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

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

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

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

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

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

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

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

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

Ответ 5

Людям, которые утверждают, что это то же самое, что TSP, вам нужно отозвать свою степень. Пятиклассник может написать доказательство, которое показывает, что это не O (n ^ 2 2 ^ n). Круговая траектория - это не та же самая проблема, что и кратчайшая между всеми точками.

Вы анафема для CS, если вы верите или утверждаете иначе, вернитесь и изучите свое ремесло.