Кратчайший маршрут, начиная и заканчивая где угодно

Question

Я ищу алгоритм, который соединит большое количество географических координат (100-1000), создавая кратчайший возможный маршрут между ними, начиная с любого места и заканчивая где-нибудь еще.Я работаю с Python.

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

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

Алгоритм Прима:

Алгоритм Крускала:

Желаемый результатосновано на Prim / Kruskal, но с использованием логики TSP (пример нарисован от руки, не оптимизирован):

Answer 1

Если вам не нужно производственное решение, напишите Python, чтобы вывести свою матрицу расстояний в формате TSPLIB с дополнительным городом (представляющим место, куда вы будете отправляться в Uber) с нулевым расстоянием до каждого другого города.Затем подайте его (например) Concorde или LKH .

Answer 2

Prim и Kruskal - это алгоритмы для поиска связующего дерева.Вы пытаетесь решить известный вариант TS (задача коммивояжера), в котором вы не возвращаетесь к исходной точке.

Местоположение вашего дома не имеет значения, согласно вашему определению.Ваша определенная проблема состоит в том, чтобы посещать каждое место с наименьшим пройденным расстоянием, без возврата к исходной точке.Это хорошо описано в «литературе».

Решение «быстрого удара» состоит в том, чтобы взять любое стандартное решение TS и удалить самый длинный сегмент.Это хорошая эвристика, хотя она не гарантирует оптимального решения.