双向A* (A-star)搜索

Question

我正在实现双向A*搜索(在搜索中，双向搜索是同时从源和目标执行的，当这两个搜索相遇时，我将获得最短路径-至少添加了一些额外的逻辑)。

有没有人有过单向A*和双向A*的经验？它--我能期待什么样的性能提升？我曾估计它或多或少会减少搜索时间的一半，至少--但我能看到比这更大的收益吗？我正在使用算法来确定公路网上的最短路径-如果这与此相关的话(我已经读到了MS的"Reach“算法，但我想逐步实现这一点，而不是直接跳进去)。

Answer 1

在最好的情况下，它将以O(b^(n/2))运行，而不是O(b^n)，但这仅在您幸运的情况下:)

(其中b是分支因子，n是a单向A*考虑的节点数)

这完全取决于这两个搜索相遇的难易程度，如果它们在搜索的早期找到对方，你已经节省了大量的搜索时间，但如果它们分支到非常不同的方向，你可能会得到比简单的A*更慢的结果(因为所有额外的记账)

Answer 2

你可能想尝试https://github.com/sroycode/tway，有一个基准测试脚本将其与标准astar进行比较(对于NY城市道路数据，它似乎提供了30%的时间效益)

Answer 3

你可能会认为集群是更有效的助推器。另请参阅this article