algorithm - 在 3 维空间中设置封面

Question

我需要帮助构建以下问题的算法。

我有一组点G，可以“看到”其他点C。需要一种算法从 G 中找到覆盖所有 C 的最小集合(G 不一定是 C 的一部分) ).

我觉得这应该用动态规划来解决。但我愿意接受任何可以帮助我的解决方案/想法。

谢谢!

编辑 1:

我可能没有完全理解这个问题。

这些点位于具有地形高度的 3d 表面上。地形可能会上升到点之间的某个高度，使得一个点看不到另一个点。只要有一条直线，无论距离多远，这些点都可以看到彼此。

• 如果点a(来自G)可以看到点b(来自C)-点b可以看到d(从C)，然后a可以看到d。不确定这是否会产生影响。

• 如果只有a(来自G)可以看到b(来自C)，我们必须选择 a 以覆盖所有 C - 所以最好在使用贪心算法之前这样做。

还在考虑根据新信息是否还有其他差异。

Answer 1

你的问题叫做Set cover problem .它是 NP 完全的。

我会使用贪婪的 log(n) 近似算法。它在每一步选择 (G) 中覆盖 (C) 中仍未覆盖的最大点数的元素。

---

在 Internet 上找到的大多数讲义仅显示上述近似算法。

Lund & Yannakakis (1994) 已经证明，很难比上面的算法做得更好。您可以在维基百科文章中找到引用。

您还可以使用集合覆盖问题的等效整数线性问题公式。但是你又得到了一个 log(n) 近似算法。

还有其他的逼近算法，但大多数都在研究论文中，所以他们的描述并不是很容易理解。您可以通过谷歌搜索“近似算法集封面”找到它们

---

我不知道是否有经验法则可以判断问题是 NP 完全问题还是已知问题的变体 ti 存在使用动态规划的解决方案。但是我发了一个问题here .

---

关于只有a(来自G)可以看到b(来自C)的情况，无论如何，贪心算法都会选择 a，因为它只会在看到 C 中的所有点时停止。算法选择点的顺序不会改变解决方案。

---

事实上，如果点 a(来自 G)可以看到点 b(来自 C)-而点b可以看到d(来自C)，那么a可以看到d，不允许问题成为模特广告 planar graph .平面图对您的问题有更好的近似算法，比贪心算法更好。