python-2.7 - 给定一组点，找到最小的点子集，从中可以画出直径为 n 的圆来包含所有点

Question

我有一个包含相关纬度/经度数据（站点）的地点列表。我试图找到最少的访问站点的基地（最大限度地减少旅行发生）。有任何想法吗？我大部分时间都在使用 Python (2.7.3)，但欢迎提供任何建议/示例。

Answer 1

这可以看作是集合覆盖问题。

使用维基百科的术语，你的宇宙将是城市。如果有m城市，就会有m集。k-th 集将对应于k-th 城市，并将包括所需旅行半径范围内的所有城市k，包括k它自己。任务是找到覆盖宇宙的最少数量的集合（换句话说，你可以到达宇宙中每个城市的最少城市）。

坏消息是这个问题是 NP 难的。但是，有启发式方法。