我正在实现双向 A* 搜索（双向搜索，因为搜索是同时从起点和终点执行的，当这两个搜索相遇时，我将获得最短路径 - 至少加入一些额外的逻辑）。
有没有人有任何使用单向 A* 和双向化（！）它的经验 - 我可以期待什么样的性能提升？我估计它或多或少地将搜索时间减半，至少 - 但我可以看到更大的收益吗？我正在使用该算法来确定道路网络上的最短路线 - 如果这有任何相关性（我已经阅读了 MS 的“Reach”算法，但想朝着这个方向迈出一小步，而不是直接跳进去）。
问问题
13464 次
3 回答
9
在最好的情况下，它会在 O(b^(n/2)) 而不是 O(b^n) 中运行，但前提是你很幸运 :)
（其中 b 是您的分支因子，n 是单向 A* 会考虑的节点数）
这完全取决于两个搜索相遇的难易程度，如果他们在搜索的早期就在一个好的中点找到了对方，那么你就省去了很多搜索时间，但是如果它们分支到截然不同的方向，你最终可能会得到比简单的 A* 慢的东西（因为所有额外的簿记）
于 2010-09-04T10:49:23.243 回答
2
您可能想尝试https://github.com/sroycode/tway 有一个基准脚本将其与标准 astar 进行比较（对于纽约城市道路数据，它似乎提供了 30% 的时间收益）
于 2012-09-04T14:20:56.930 回答
1
您可以将集群视为更有效的助推器。另见这篇文章
于 2016-06-09T11:10:10.743 回答