Двунаправленный A * (A-star) Поиск
Я реализую двунаправленный поиск A * (двунаправленный, как в поиске, выполняется как из источника, так и из пункта назначения одновременно, и когда эти два поиска встречаются, у меня будет мой самый короткий путь - по крайней мере, с небольшим количеством дополнительных логика брошена).
Есть ли у кого-нибудь опыт использования однонаправленного A * и двунаправленного (!) - какого рода прирост производительности я могу ожидать? Я рассчитывал на это более или менее, уменьшая вдвое время поиска, как минимум, но могу ли я увидеть большие выгоды, что это? Я использую алгоритм для определения кратчайших маршрутов в дорожной сети - если это в какой-то мере актуально (я читал о алгоритме MS "Reach", но хочу сделать шаги для этого, а не прыгать прямо).
Ответы
Ответ 1
В лучшем случае он будет работать в O (b ^ (n/2)) вместо O (b ^ n), но это только, если вам повезло:)
(где b - ваш коэффициент ветвления, а n - количество узлов, которые рассмотрит однонаправленный A *)
Все зависит от того, насколько легко встречаются два поисковых запроса, если они находят друг друга на хорошем полпути в начале поиска, который вы проделали с большим количеством времени поиска, но если они вступают в дико разные направления, вы можете в конечном итоге с чем-то медленнее, чем простой A * (из-за всей дополнительной бухгалтерии)
Ответ 2
Вы можете попробовать http://sourceforge.net/projects/tway/
есть бенчмаркинг script, который сравнивает это со стандартным astar
(для данных городских дорог в Нью-Йорке, похоже, он дает 30-процентную выгоду)
Ответ 3
Внедрили 3 разных двунаправленных алгоритма поиска A * (см. cskit).
Чтобы увидеть алгоритмы в действии, от корневого типа проекта mvn exec:java (требуется Maven).
Удачи!
( Изменить: Эта библиотека предоставляет 3 разных двунаправленных алгоритма A *. Все три являются оптимальными.)
Ответ 4
Вы можете рассматривать кластеризацию как более эффективный усилитель. Также см. в этой статье
