Алгоритм сортировки для нескольких списков двумерных точек

Question

Мне нужен алгоритм для сортировки нескольких списков точек в 2D-плоскости, чтобы соответствующие точки каждого списка минимизировали расстояние между ними.

т.е. для двух списков одинаковой длины, первая точка первого списка имеет минимальное расстояние до первой точки второго списка, вторая точки из первых имеют минимальное расстояние до второй точки второй, и т.д.

Моя первая мысль состояла в том, чтобы просто отсортировать по средним координатам x и y, но я чувствую, что это не совсем точно.

Answer 1

Если вы пытаетесь минимизировать общие расстояния между соседними точками, это вовсе не задача сортировки.

Вместо этого, похоже, вы пытаетесь решить проблему Hamiltonian Path в двумерном пространстве. Это NP-полное для произвольных расстояний между точками. Даже ограничение на евклидовы расстояния, в вашем случае, is still NP-complete, но есть алгоритмы аппроксимации; см. https://www.ads.tuwien.ac.at/teaching/ws10/AlgGraphen/ag3-2x2.pdf. В общем, евклидово TSP можно аппроксимировать за полиномиальное время благодаря работе Санджив Арора, для которого он выиграл Gödel Prize:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6765

Поиск по евклидовой коммивояжера проблемы, и вы также получите ссылки на другие научные статьи, в которых обсуждается, как приблизить решение этого.