Добавление путевых точек к поиску графиков A *

Question

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

Пример:

Я хочу пройти из пункта 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

Затем для каждой перестановки я вычисляю маршрут A * от первого до второго, затем добавляю его к маршруту от второго до третьего, затем с третьего по четвертый.

Когда я вычисляю это для каждой перестановки, я сортирую маршруты по расстоянию и возвращаю самое короткое.

Очевидно, это работает, но требует большого количества вычислений и полностью рушится, когда у меня есть 6 путевых точек (перестановка из 8 пунктов равна 40320: -))

Есть ли лучший способ сделать это?

Answer 1

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

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

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

Answer 2

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

Существует лучший способ, чем тот, который вы используете.Ультрасовременный решатель TSP принадлежит Решателю Concorde от Georgia Tech .Если вы не можете просто использовать их свободно доступные программы самостоятельно или использовать их API, я могу описать основные методы, которые они используют.

Чтобы решить TSP, они начинают с жадной эвристики, называемой Лин-Керниганэвристика для генерации верхней границы.Затем они используют ветвление и вырезание в смешанной целочисленной программной формулировке TSP.Это означает, что они пишут ряд линейных и целочисленных ограничений, которые, когда они решены, дают вам оптимальный путь TSP.Их внутренний цикл вызывает решатель линейного программирования, такой как Qsopt или Cplex, чтобы получить нижнюю границу.

Как я уже говорил, это современный уровень, так что если вы ищете лучший способрешить TSP, чем то, что вы делаете, здесь самое лучшее.Они могут обрабатывать более 10 000 городов за несколько секунд, особенно на симметричном, плоском TSP (я подозреваю, что это вариант, над которым вы работаете).

Если число путевых точек, которые вам нужно в конечном итоге обработать, малоскажем, порядка от 10 до 15, тогда вы сможете выполнять поиск по ветвям и границам, используя минимальную эвристику связующего дерева .Это учебное упражнение во многих вводных курсах по искусственному интеллекту.Больше точек, чем вы, вероятно, переживете фактическое время работы алгоритма, и вместо этого вам придется использовать Concorde.