我正在实现一个双向A *搜索（双向搜索是同时从原点和目的地执行的，当这两个搜索相遇时，我会得到最短的搜索路径 - 至少有一些额外的逻辑抛出）。双向A *（A-star）搜索
有没有人有任何单向A *和双向化（！）的经验 - 我可以期待什么样的性能增益？我认为这或多或少地将搜索时间缩短了一半，但至少我能看到更大的收益吗？我正在使用该算法来确定道路网络上的最短路线 - 如果这与任何方式相关（我已阅读MS的“到达”算法，但希望采取婴儿步骤而不是直接跳跃）。
在最好的情况下，可能它会为O运行（B ^（N/2）），而不是Ø（B^N），但这只是如果你运气好:)
（其中b是你的分支因子，n是单向A *会考虑的节点数量）
这一切都取决于两个搜索如何轻松相遇，如果他们在搜索的早期发现彼此处于良好的中途点但是如果他们分歧到极其不同的方向，你可能会得到比简单A *慢的东西（因为所有额外的簿记）
感谢迈克尔 - 一些额外的研究表明，我“不太可能是幸运的 - 双向A *在两个方向收敛在同一个节点上据说相当尴尬。我可能会放弃它，或者更可能会投入一些时间来计算覆盖范围。 – 2010-09-05 05:13:40
数字越大，您在进行双向搜索时就会赢得胜利。微软研究院实验室使用这种算法，但有很多更复杂的改进。 – 2011-05-27 21:14:10
你可能会蚂蚁尝试http://sourceforge.net/projects/tway/ 存在与标准爱仕达 比较该基准测试脚本（纽约城市道路数据似乎给予30％的时间效益）
已经实现了3种不同的双向A *搜索交易算法（参见cskit） 。
net.coderodde.cskit.graph.p2psp.general.FastSuboptimalFinder是最快的，但不是最优的;net.coderodde.cskit.graph.p2psp.general.BHPAFinder是最优和相当快;如果最优性是要求，我会用这个;net.coderodde.cskit.graph.p2psp.general.WhangboFinder不是特别好。要查看运行中的算法，请从项目根类型mvn exec:java（需要Maven）中查看。 祝你好运！
（编辑：This library提供3种不同的双向A *算法三个都是最优的。）
您可以考虑作为集群更有效助推器。另请参阅this article
注 - 问题标题以单词形式重复A *以便于搜索。 – 2010-09-04 09:55:00
供参考：这是链接到达到A *（A-星级）的MS论文的链接：http://www.avglab.com/andrew/pub/alenex06.pdf – shindigo 2011-03-14 17:00:28