我需要帮助构建以下问题的算法。
我有一组点G可以“看到”其他点C。需要一种算法来从G中找到覆盖所有C的最小集合（G不一定是C的一部分）。
我有一种感觉，这应该通过动态编程来解决。但我对任何可以帮助我的解决方案/想法持开放态度。
谢谢！
编辑1：
我可能没有完全理解这个问题。
这些点位于具有地形高度的 3d 表面上。地形可能会在点之间上升到一定高度，使得一个点看不到另一个点。只要有直接的视线，无论距离多远，这些点都可以互相看到。
如果点a（从G）可以看到点b（从C）-并且点b可以看到d（从C），那么a可以看到d。不确定这是否有所作为。
如果只有a（来自G）可以看到b（来自C），我们必须选择a以覆盖所有C - 所以在使用贪心算法之前最好这样做。
根据新信息，仍在考虑是否还有其他差异。
您的问题称为Set cover problem。它是NP完全的。
我会使用一个贪婪的 log( n ) 近似算法。它在每一步都选择 (G) 中覆盖 (C) 中仍未覆盖的最大点数的元素。
在 Internet 上找到的大多数讲义仅显示上述近似算法。
正如 Lund & Yannakakis (1994) 所证明的，很难比上面的算法做得更好。您可以在 wikipedia 文章中找到参考资料。
您还可以使用集合覆盖问题的等效整数线性问题公式。但是你又得到了一个 log(n) 近似算法。
还有其他的近似算法，但大多数都在研究论文中，因此它们的描述并不是很容易理解。你可以找到他们只是谷歌搜索“近似算法集封面”
我不知道是否有经验法则可以知道问题是 NP 完全问题还是已知问题 ti 的变体，其中存在使用动态编程的解决方案。但我在这里发布了一个问题。
关于只有a（来自G）可以看到b（来自C）的情况，贪心算法无论如何都会选择a ，因为它只有在看到来自C的所有点时才会停止。算法选择点的顺序不会改变解。
如果点a（从G）可以看到点b（从C）并且点b可以看到d（从C），那么 a 可以看到d，这一事实不允许将问题建模为平面图。平面图对您的问题有更好的近似算法，比贪心算法更好。