Больше чем один путь от A *?

Question

Я написал A *, который хорошо работает.Это дает мне кратчайший путь между двумя узлами.Тем не менее, я хотел бы иметь два или даже три пути.Лучший, второй лучший и третий путь (если доступно более одного пути).Что-то вроде указаний на Картах Google, где вы можете увидеть несколько вариантов между двумя городами.

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

Моя реализация A * взята из псевдокода в Википедии (http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode), и написана на VB .NET.Если это имеет какое-либо значение.

Спасибо.

Answer 1

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

Но вы можете получить другие результаты: иногда пути могут отличаться только в последнем ребре.Вот так: ------- <=> конец.Если есть действительно другой лучший путь с аналогичной длиной, то вы его найдете.

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

Answer 2

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

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

Затем вы можете создать компромисс между самым коротким и самым быстрым. Теперь у вас есть три (возможно) разных маршрута.

Другие опции:

(i) добавить вес к каждой дуге, чтобы учесть соединения в начале и в конце; возиться с этим весом, что позволяет создавать маршруты, которые сводят к минимуму повороты. Вы также можете добавить дополнительные веса для очень крутых поворотов или поворотов по транспортному потоку (правые повороты в Великобритании, Австралии, Индии и т. Д .; левые повороты в США, Франции и т. Д.).

(ii) Создайте маршрут, обходящий автомагистрали / автострады, установив для них стоимость очень высокого значения.

(iii) Использование времени суток или фактической оперативной информации для оценки потока трафика и изменения весовых коэффициентов на его основе.

Answer 3

Для получения точного второго кратчайшего пути требуется что-то вроде this .

Если вам не важна такая точность, вы можете ввести немного случайности в кратчайший путь:

1. Вырезать вершину или ребро из кратчайшего пути и заново вычислить.
2. В какой-то момент по кратчайшему пути совершите намеренный неправильный поворот куда-нибудь и пересчитайте оттуда.