algorithm - 双向 A*(A 星)搜索

Question

我正在实现双向 A* 搜索(双向搜索是同时从起点和终点执行的，当这两个搜索相遇时，我将获得最短路径 - 至少有一点额外逻辑被抛出)。

有没有人有使用单向 A* 和双向化(!)它的经验 - 我可以期待什么样的性能提升？我估计至少将搜索时间减半 - 但我可以看到更大的 yield 吗？我正在使用该算法来确定道路网络上的最短路线 - 如果这在任何方面都相关(我已经阅读了 MS 的“Reach”算法，但想朝着这个方向迈出一小步而不是直接跳进去)。

Answer 1

在最好的情况下，它会在 O(b^(n/2)) 中运行而不是 O(b^n)，但这只是在你幸运的情况下:)

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

这完全取决于两个搜索相遇的难易程度，如果它们在搜索的早期在一个好的中间点找到对方，您就可以省去大量搜索时间，但如果它们分支到截然不同的方向，您可能最终得到比简单 A* 更慢的结果(因为所有额外的簿记)