Добавление waypoints к* поиск графика
У меня есть способность вычислить оптимальный маршрут между запуском и конечной точкой с помощью A*. Прямо сейчас я включаю waypoints между своим запуском и конечными точками путем применения* к парам во всех перестановках моих точек.
Пример:
Я хочу заставить от точки 1 указывать 4. Кроме того, я хочу пройти через точки 2 и 3.
Я вычисляю перестановки (1, 2, 3, 4):
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
Затем для каждой перестановки я вычисляю* маршрут сначала к второму, затем добавляю его к маршруту от второго до третьего, затем третье к четвертому.
Когда я имею, это вычислило для каждой перестановки, я сортирую маршруты по расстоянию и возвращаю самое короткое.
Очевидно, это работает, но включает большое вычисление и полностью выходит из строя, когда у меня есть 6 waypoints (перестановки 8 объектов 40320 :-))
Существует ли лучший способ сделать это?
2 ответа
Прежде всего, вы должны хранить все промежуточные вычисления. Как только вы рассчитали маршрут от 1 до 2, вы никогда не должны пересчитывать его снова, просто посмотрите в таблице. Во-вторых, если ваш граф ненаправленный, то маршрут из 2 в 1 имеет точно такое же расстояние, как и маршрут из 1 в 2, поэтому его тоже не следует пересчитывать.
И, наконец, в любом случае алгоритм будет экспоненциальным по отношению к количеству точек, которые вам нужно пройти. Это очень похоже на проблему путешествующего продавца, и это будет именно эта проблема, если вы включите все доступные точки. Эта проблема NP-полна, то есть имеет сложность, экспоненциальную от числа путевых точек.
Так что если у вас много точек, которые вы должны пройти, экспоненциальный коллапс неизбежен.
Как упоминалось в предыдущем ответе, эта проблема является NP-полной проблемой коммивояжера.
Есть метод получше, чем тот, которым вы пользуетесь. Современный решатель TSP создан решателем Concorde Georgia Tech . Если вы не можете просто использовать их свободно доступную программу в своей собственной или использовать их API, я могу описать основные методы, которые они используют.
Чтобы решить TSP, они начинают с жадной эвристики, называемой эвристикой Лин-Кернигана, для получения верхней границы. Затем они используют метод ветвления и отсечения в формулировке ПБО смешанного целочисленного программирования. Это означает, что они записывают серию линейных и целочисленных ограничений, решение которых дает вам оптимальный путь TSP. Их внутренний цикл вызывает решатель линейного программирования, такой как Qsopt или Cplex, для получения нижней границы.
Как я уже упоминал, это самое современное решение, поэтому, если вы ищете лучший способ решить TSP, чем то, что вы делаете, вот лучший. Они могут обрабатывать более 10 000 городов за несколько секунд, особенно в симметричном, плоском TSP (я подозреваю, что это вариант, над которым вы работаете).
Если количество путевых точек, которые вам в конечном итоге необходимо обработать, невелико, скажем, порядка 10–15, то вы можете выполнить поиск по ветвям и границам, используя эвристику минимального связующего дерева . Это упражнение из учебника для многих вводных курсов по ИИ. Больше путевых точек вы, вероятно, переживете фактическое время работы алгоритма, и вместо этого вам придется использовать Concorde.