我正在研究一些双向 A* 算法。我从头到尾，从头到尾搜索。当第一个线程遇到来自其他线程（来自打开或关闭列表）的节点时，它会停止并绘制一条返回路径。
但是当线程采用不同的路径并且它们没有在应有的位置相遇时，我遇到了问题。
示例：http: //i.imgur.com/ittIAlI.png
问问题
3140 次
1 回答
6
这是一个阻碍双向搜索研究的常见问题，直到 Kaindl & Kainz 在 1997 年证明没有必要。PNBA* 的第 2.3 节：并行双向启发式搜索算法提供了额外的历史背景，以及克服这一问题的（并行）双向算法问题。
您可能希望首先阅读另一种最短路径的双向算法，因为它描述的（串行） NBA*算法在第一篇论文中被广泛引用。
我刚刚成功地调整了我在此处找到的开源 Hexgrid PathFinding 实用程序，以使用 PNBA* 的串行版本。（实际上大约介于 NBA* 和 PNBA* 之间）这将在一两天内上传。
使最短路径更快给出了使用双向 A* 和预处理开发 Bing 地图路径查找器的概述。Reach for A* and Better Landmarks Within Reach中提供了预处理工作的详细描述以及相关算法的使用
于 2013-07-03T01:01:57.927 回答