双向 A*（A 星）搜索
我正在实现双向 A* 搜索（双向搜索是同时从起点和目的地执行的，当这两个搜索相遇时，我将得到最短路径 - 至少会抛出一些额外的逻辑）。
有谁有使用单向 A* 和双向化（！）它的经验 - 我可以期望什么样的性能增益？我认为它至少可以将搜索时间减少一半 - 但我可以看到比这更大的收益吗？我正在使用该算法来确定道路网络上的最短路线 - 如果这有任何相关性（我已经阅读过有关 MS 的“Reach”算法，但希望朝着这个方向迈出一小步，而不是直接跳进去）。
I'm implementing a bidirectional A* search (bidirectional as in the search is performed from both the origin and destination simultaneously, and when these two searches meet, I'll have my shortest path - at least with a bit of extra logic thrown in).
Does anyone have any experience with taking a unidirectional A* and bidirectionalising(!) it - what sort of performance gain can I expect? I'd reckoned on it more-or-less halving the search time, at a minimum - but may I see bigger gains that this? I'm using the algorithm to determine shortest routes on a road network - if that's in any way relevant (I've read about MS's "Reach" algorithm, but want to take baby-steps towards this rather than jumping straight in).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
在最好的情况下，它会以 O(b^(n/2)) 而不是 O(b^n) 运行，但前提是你很幸运:)
（其中 b 是你的分支因子，n 是单向 A* 会考虑的节点数）
这完全取决于两个搜索相遇的难易程度，如果它们在搜索早期的良好中间点找到彼此，那么您就节省了很多搜索时间，但如果它们分支到截然不同的方向，你最终可能会得到比简单的 A* 慢的东西（因为所有额外的簿记）
In the best possible case it'd run in O(b^(n/2)) instead of O(b^n), but that's only if you're lucky :)
(where b is your branching factor and n is the number of nodes a unidirectional A* would consider)
It all depends on how easily the two searches meet, if they find each other at a good halfway point early in the search you've done away with a lot of search time, but if they branch into wildly different directions you may end up with something slower than simple A* (because of all the extra bookkeeping)
您可能想尝试 https://github.com/sroycode/tway
有一个基准测试脚本可以将其与标准 astar 进行比较
（对于纽约城市道路数据，它似乎提供了 30% 的时间效益）
You may want to try https://github.com/sroycode/tway
there is a benchmarking script that compares this with standard astar
( for NY city roads data it seems to give a 30% time benefit )
您可能会认为集群是更有效的助推器。另请参阅 这篇文章
You may consider clustering as much more efficient booster. Also see this article