点覆盖问题

Question

最近,我在测试此问题:给定一组点米(全部在x轴)和一组 Ñ与端点[线的L,R ](再次在x轴),找到的最小子集n使得所有点都被一条线覆盖.证明您的解决方案始终找到最小子集.

我为它写的算法是这样的结果:(说行存储为数组,左端点位于0位,右端位于位置1)

algorithm coverPoints(set[] m, set[][] n):
    chosenLines = []
    while m is not empty:
        minX = min(m)
        bestLine = n[0]
        for i=1 to length of n:
            if n[i][0] <= minX and n[i][1] > bestLine[1] then
                bestLine = n[i]
        add bestLine to chosenLines
        for i=0 to length of m:
            if m[i] <= bestLine[1] then delete m[i] from m
    return chosenLines

我只是不确定这总是找到最小的解决方案.这是一个简单的贪婪算法,所以我的直觉告诉我它不会,但我的一个比我好得多的朋友说,对于这个问题,像这样的贪婪算法总能找到最小的解决方案.为了证明我的总是找到最小的解决方案我做了一个非常手的波浪证明矛盾,我做了一个假设,可能根本不是真的.我完全忘记了我的所作所为.

如果这不是一个最小的解决方案,有没有办法在比O(n!)时间更少的时间内完成它？

谢谢

Answer 1

你的贪婪算法是正确的.我们可以通过显示任何其他覆盖只能通过用您的算法生成的覆盖替换它来改进来证明这一点.

设C是给定输入的有效覆盖(不一定是最优的),并根据您的算法使S成为覆盖.现在让我们检查点p1,p2,... pk,它们代表你在每个迭代步骤中处理的最小点.覆盖物C也必须覆盖它们.观察到C中没有任何部分覆盖其中两个点; 否则,你的算法会选择这个细分!因此,| C |> = k.算法中的成本(段数)是多少？| S | = K.

这完成了证明.

两个笔记:

1)实现:用n [0]初始化bestLine是不正确的,因为循环可能无法改进它,并且n [0]不一定覆盖minX.

2)实际上这个问题是Set Cover问题的简化版本.虽然原始是NP完全的,但这种变化导致多项式.