7

我最近在测试中遇到了这个问题：给定一组点m（都在 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!) 的时间内完成它？

谢谢

4

2 回答 2

7

你的贪心算法是正确的。我们可以通过证明任何其他覆盖物只能通过将其替换为您的算法产生的覆盖物来证明这一点。

让 C 成为给定输入的有效覆盖（不一定是最佳输入），并根据您的算法让 S 成为覆盖。现在让我们检查点 p1, p2, ... pk，它们代表您在每个迭代步骤中处理的最小点。覆盖物 C 也必须覆盖它们。观察 C 中没有包含其中两个点的段；否则，您的算法将选择此段！因此，|C|>=k。你的算法的成本（段数）是多少？|S|=k。

这样就完成了证明。

两个注意事项：

1）实现：用n[0]初始化bestLine是不正确的，因为循环可能无法改进它，而n[0]不一定覆盖minX。

2) 实际上这个问题是Set Cover问题的简化版本。虽然原件是 NP 完全的，但这种变化结果是多项式的。

于 2010-05-12T20:46:09.073 回答
0

提示：首先尝试证明您的算法适用于大小为 0、1、2... 的集合，看看您是否可以将其概括为通过归纳创建证明。

于 2010-05-12T18:38:53.383 回答