Функция для расчета наименьшего набора почтовых индексов, в котором все почтовые индексы находятся в пределах х миль

Question

Мне нужна функция (на любом языке, но предпочтительно в скрипте), которая может принимать массив объектов (скажем, почтовых индексов) с координатами широты / долготы и возвращать наименьшее подмножество, в котором все элементы исходного массива находятся в пределах x(скажем, 20) миль хотя бы 1 члена подмножества.

Answer 1

Вот жадный алгоритм, с которого можно начать.

1. Начните с пустого набора результатов R и позвольте S быть набором всех почтовых индексов.
2. Для каждого почтового индекса Zn в S , вычислить набор Vn почтовых индексов, которые находятся в пределах 20 миль от Zn .
3. Найдите набор Vmax с наибольшим количеством элементов - Добавьте соответствующий почтовый индекс Zmax в набор результатов R и удалите все элементы Vmax от S .
4. С остальными элементами в S повторять с шага 2 до тех пор, пока S не станет пустым. Тогда окончательный набор будет R .