Алгоритм: кратчайший путь между всеми точками

Question

Предположим, у меня есть 10 баллов. Я знаю расстояние между каждой точкой.

Мне нужно найти кратчайший маршрут, проходящий через все точки.

Я попробовал пару алгоритмов (Дейкстра, Флойд Варшалл, ...), и все они дают мне кратчайший путь между началом и концом, но они не прокладывают маршрут со всеми точками на нем.

Перестановки работают нормально, но они слишком дороги.

Какие алгоритмы вы можете посоветовать мне изучить для этой проблемы? Или есть документированный способ сделать это с помощью вышеупомянутых алгоритмов?

Answer 1

Посмотрите на проблему коммивояжера .

Возможно, вы захотите взглянуть на некоторые из эвристических решений . Возможно, они не смогут дать вам 100% точных результатов, но часто они могут предложить достаточно хорошие решения (от 2 до 3% от оптимальных решений) в разумные сроки.

Answer 2

Это, очевидно, проблема коммивояжера . Специально для N=10 вы можете либо попробовать наивный алгоритм O(N!), либо, используя Dynamic Programming , вы можете уменьшить его до O(n^2 2^n) в торговом пространстве.

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

Answer 3

Как уже упоминали другие, это экземпляр TSP. Я думаю, Конкорд , разработанный в Джорджии, является современным решением проблемы. Он может обрабатывать более 10000 точек в течение нескольких секунд. Он также имеет API, с которым легко работать.

Answer 4

Я думаю, это то, что вы ищете, на самом деле:

Флойд Варшалл

В информатике алгоритм Флойда – Варшалла (иногда известный как алгоритм WFI [требуется уточнение], алгоритм Роя – Флойда или просто Алгоритм Флойда) - это алгоритм анализа графа для нахождения кратчайшего пути в взвешенном графе (с положительным или отрицательным весом ребер). одиночное выполнение алгоритма найдет длины (суммируются веса) кратчайших путей между всеми парами вершин, хотя это не возвращает детали самих путей

В подразделе «Восстановление пути» объясняется структура данных, в которой вы должны хранить «пути» (на самом деле вы просто сохраняете следующий узел для перехода, а затем тривиально восстанавливаете тот путь, который требуется по мере необходимости).