Пусть p = ceil (N / 64).
Это оптимальное количество оборудования.
Пусть s = ceil (sqrt (p)).
Сортировать данные по оси х.Нарезать данные на кусочки по 64 * s записей каждый (но последний слайд).
В каждом срезе сортировать данные по оси y.Возьмите 64 предмета каждый и назначьте их одному оборудованию.Легко видеть, что все, кроме, возможно, последнего оборудования используются оптимально и близко.
Сортировка настолько невероятно дешева, что это будет очень быстро.Попробуйте, и вы, вероятно, будете удивлены компромиссом между качеством и временем выполнения!Я не удивлюсь, если он найдет конкурентные результаты для большинства из тех, что вы пробовали, за исключением подхода ЛП, и он запустится всего за несколько секунд.
В качестве альтернативы: сортируйте все объекты по их координате кривой Гильберта.Разбейте на p разделы, назначьте одно оборудование каждому.
Второе намного сложнее реализовать и, вероятно, медленнее.Иногда это может быть лучше, но иногда и хуже.
Если вам важнее расстояние, попробуйте следующую стратегию: создайте пространственный индекс (например, kd-tree или, если у вас есть Haversine, R *)-tree).Для каждой точки найдите 63 ближайших соседей и сохраните их.Сортировать по расстоянию по убыванию.Это даст вам оценку «сложности».Теперь не размещайте снаряжение в самой трудной точке, а рядом - у соседа с наименьшим максимумом (расстояние до трудной точки, расстояние до 63 ближайшего соседа).Повторите это для нескольких пунктов, но после примерно 10% данных, начните снова всю процедуру с оставшимися точками.Проблема в том, что вы не очень точно указали, когда предпочитаете, чтобы расстояния были небольшими, даже при использовании большего количества оборудования ... Вы можете включить это, рассматривая только соседей в пределах определенной границы.Точка с наименьшим количеством соседей в пределах границы является самой сложной;и лучше всего его покрывает сосед с наиболее непокрытыми точками в пределах границ и т. д.