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

Question

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

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

Answer 1

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

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

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

Answer 2

Вы можете w муравей попробовать http://sourceforge.net/projects/tway/ есть бенчмаркинг сценарий, который сравнивает со стандартным ASTAR (для NY данных городских дорог, кажется, дает преимущество по времени 30%)

Answer 3

внедрило 3 разных двунаправленной A * Поиск Algos (см 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). Удачи!

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

Answer 4

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