Как найти все возможные пути между двумя вершинами

Question

Я отлаживаю унаследованный код, где сеть дорог была представлена ​​Boost Graph. A_Star поиск не дает мне кратчайшего пути между двумя определенными точками, и я знаю, что boost не может быть ошибкой (не до тех пор, пока я не отлаживал свой код тысячу раз).

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

Я ценю вашу любезную помощь и комментариям

Answer 1

А * на основе эвристики. Если наследие использует A *, это означает, что проблема более сложная, а затем найдите самый короткий путь.

Чтобы найти кратчайший путь между двумя вершинами, существуют определенные алгоритмы графа, Dijkstra - самый простой для реализации (обязательно сделайте это с проверкой цикла). Они детерминированы.

Если вам нужно знать ВСЕ пути между двумя вершинами, этот NP является полным, что означает, что вам нужно вернуться с обратным отсчетом.

A * обычно используется для решения проблем с NP. Результаты не являются ЛУЧШИМ путем, это всего лишь ОЧЕНЬ ХОРОШИЙ ХОРОШИЙ ПУТЬ, НАХОДЯЩИЙСЯ В ПОСТОЯННОМ ВРЕМЕНИ.

Эвристика из A * используется для удаления рекурсий или преобразования алгоритма из обратного отсчета в первый поиск (обычно последний).

Пример разницы между задачей решается с помощью A * алгоритма и Дейкстров будет следующие (от верхней части моей головы):

• Найти самые короткие дороги в Manhatan от Corner X, Y к углу X1, Y1 (разрешается Dijkstra или в случае Manhatan BFS)

• Выберите лучший маршрут в Манхатане из угла X, Y в угол X1, Y1 с учетом трафика и светофоров в соответствии с определенными часами (так что это существенная разница между стоимостью для края 1,1 - 1,2, если вы достигнете 1,1 при t0, и если вы достигнете 1,1 при t1> t0, exa mple: эта часть дороги блокируется при t1 в течение 10 часов).