algorithm - 点覆盖问题

Question

我最近在测试中遇到了这个问题:给定一组点 m(全部在 x 轴上)和一组 n 端点为 [< em>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

我只是不确定这是否总能找到最小解。这是一个简单的贪心算法，所以我的直觉告诉我它不会，但是我的一个 friend 在这方面比我好得多，他说对于这个问题，像这样的贪心算法总能找到最小解。为了证明我的总是找到最小的解决方案，我做了一个非常手工的矛盾证明，我做了一个可能根本不正确的假设。我完全忘记了我做了什么。

如果这不是一个最小的解决方案，有没有办法在不到 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 完全的，但这种变化结果是多项式的。