python-2.7 - Given a set of points, find smallest subset of points from which circles of n diameter can be drawn to encompass all points

Question

I've got a list of places with associated lat/lon data (sites). I'm trying to find the fewest bases from which to visit the sites (minimizing travel occurrences). Any ideas? I've mostly been working with Python (2.7.3), but any suggestions/examples are welcome.

Answer 1

これはセット カバーの問題と見なすことができます。

ウィキペディアの用語を使用すると、宇宙は都市になります。m都市があれば、mセットがあります。k- 番目のセットはk- 番目の都市に対応し、 から必要な移動範囲内にあるすべての都市(それ自体kを含む) が含まkれます。タスクは、宇宙をカバーする最小数のセットを見つけることです (別の言い方をすれば、宇宙のすべての都市に到達できる都市の最小数)。

悪いニュースは、問題が NP 困難であることです。ただし、ヒューリスティックがあります。