Wil*_*l A 20 algorithm shortest-path
我正在实现双向A*搜索(双向,因为搜索同时从源和目标执行,当这两个搜索相遇时,我将拥有我的最短路径 - 至少有一些额外的逻辑抛出).
有没有人有任何采用单向A*和双向化(!)的经验 - 我可以期待什么样的性能提升？我估计它至少会将搜索时间减半或者减少 - 但是我可以看到更大的收益吗？我正在使用该算法来确定道路网络上的最短路线 - 如果这是相关的(我已经阅读了关于MS的"Reach"算法,但是想要采取婴儿步骤而不是直接进入).
在最好的情况下,它运行在O(b ^(n/2))而不是O(b ^ n),但这只有你很幸运:)
(其中b是你的分支因子,n是单向A*考虑的节点数)
这一切都取决于两个搜索相遇的容易程度,如果他们在搜索的早期阶段找到了彼此很好的搜索时间,那么如果他们分开了很多不同的搜索时间,你可能最终会遇到比简单A*慢的东西(因为所有额外的簿记)