Двунаправленный поиск A * (A-star)

Question

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

Есть ли у кого-нибудь опыт использования однонаправленного A * и двунаправленного (!) Его - какого рода увеличения производительности я могу ожидать? Я рассчитывал на это более или менее вдвое, по крайней мере, вдвое меньше времени поиска - но могу ли я увидеть большую выгоду, что это? Я использую алгоритм для определения кратчайших маршрутов в дорожной сети - если это имеет какое-либо отношение (я читал об алгоритме MS «Reach», но хочу сделать шаги в этом направлении, а не прыгать прямо).

Answer 1

В лучшем случае это будет работать в O (b ^ (n / 2)) вместо O (b ^ n), но это только если вам повезет:)

(гдеb - ваш коэффициент ветвления, а n - количество узлов, которые однонаправленный A * может рассмотреть)

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

Answer 2

Возможно, вы захотите попробовать http://sourceforge.net/projects/tway/ есть сценарий сравнения, который сравнивает его со стандартным Astar (для данных о городских дорогах Нью-Йорка это дает 30% времени)

Answer 3

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

Answer 4

Реализовано 3 различных двунаправленных алгоритма поиска A * (см. cskit ).

• net.coderodde.cskit.graph.p2psp.general.FastSuboptimalFinder - самый быстрый, но не всегда оптимальный;
• net.coderodde.cskit.graph.p2psp.general.BHPAFinder является оптимальным и довольно быстрым; если требуется оптимальность, я бы использовал это;
• net.coderodde.cskit.graph.p2psp.general.WhangboFinder не особенно хорошо.

Чтобы увидеть алгоритмы в действии, из корневого каталога проекта введите mvn exec:java (требуется Maven). Удачи!

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