点覆盖问题 [英] Point covering problem

问题描述

我最近有在测试这个问题：给定一组点的米的的（全部在x轴）和一组的 N 的线的与端点[ L，R 的]（再次对X轴），找到的最小子集的 N 的，使得所有的点都涵盖了线。证明你的解决方案总能找到最小的子集。

I recently had this problem on a test: given a set of points m (all on the x-axis) and a set n of lines with endpoints [l, r] (again on the x-axis), find the minimum subset of n such that all points are covered by a line. Prove that your solution always finds the minimum subset.

我写它的算法是东西的效果： （说行与位置0左端点和右位置1阵列存储）

The algorithm I wrote for it was something to the effect of: (say lines are stored as arrays with the left endpoint in position 0 and the right in position 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

我只是不知道这是否总能找到最小的解决方案。这是一个简单的贪心算法，所以我的直觉告诉我不会，但我的一个朋友是谁比我强多了，在这说，对这个问题的一个贪心算法，这样总能找到最小的解决方案。为了证明矿总能找到最小的解决方案，我没有用反证法一个很有一手波浪证明，我做一个假设，即可能是不正确的。我忘记了正是我所做的。

I'm just not sure if this always finds the minimum solution. It's a simple greedy algorithm so my gut tells me it won't, but one of my friends who is much better than me at this says that for this problem a greedy algorithm like this always finds the minimal solution. For proving mine always finds the minimal solution I did a very hand wavy proof by contradiction where I made an assumption that probably isn't true at all. I forget exactly what I did.

如果这不是一个最小的解决方案，是有办法做到这一点，在不到像O（N！）的时间？

If this isn't a minimal solution, is there a way to do it in less than something like O(n!) time?

感谢

推荐答案

您贪心算法的是正确的。 我们可以通过显示任何其他覆盖只能通过与您的算法产生的盖取代它来改善证明了这一点。

Your greedy algorithm IS correct. We can prove this by showing that ANY other covering can only be improved by replacing it with the cover produced by your algorithm.

设C是对于给定的输入（不一定是最佳的一种）有效的覆盖物，并令S根据你的算法是覆盖物。现在，让我们检查点P1，P2，... pk的，那些重新present你处理在每次迭代步骤的分点。覆盖Ç必须覆盖所有为好。观察到有在C中没有细分覆盖其中的两个点;否则，你的算法会选择这一领域！因此，| C |> = K。什么是成本（段计数）在你的算法？ | S | = K。

Let C be a valid covering for a given input (not necessarily an optimal one), and let S be the covering according to your algorithm. Now lets inspect the points p1, p2, ... pk, that represent the min points you deal with at each iteration step. The covering C must cover them all as well. Observe that there is no segment in C covering two of these points; otherwise, your algorithm would have chosen this segment! Therefore, |C|>=k. And what is the cost (segments count) in your algorithm? |S|=k.

这就完成了证明。

有两点需要注意：

1）实施：用正初始化bestLine [0]是不正确的，因为该环可能无法对其进行改进，和n [0]不一定覆盖其minX

1) Implementation: Initializing bestLine with n[0] is incorrect, since the loop may be unable to improve it, and n[0] does not necessarily cover minX.

2）实际上这个问题是集合覆盖的问题的简化版本。而原来是NP完全，这种变化的结果是多项式。

2) Actually this problem is a simplified version of the Set Cover problem. While the original is NP-complete, this variation results to be polynomial.

这篇关于点覆盖问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！