Rus*_*ana 3 parallel-processing a-star bidirectional path-finding
我正在研究一些双向A*算法.我正在寻找从头到尾,从头到尾.当第一个线程遇到来自其他线程(来自打开或关闭列表)的节点时,它会停止并返回一个路径.
但是当线程采用不同的路径并且它们不符合应有的位置时,我遇到了问题.
这是一个普遍的问题,阻碍了对双向搜索的研究,直到Kaindl&Kainz在1997年证明它是不必要的.PNBA*的第2.3节*:并行双向启发式搜索算法提供了额外的历史背景,以及克服这一点的(并行)双向算法问题.
您可能希望首先阅读" 另一种最短路径双向算法",因为它描述的(序列) NBA*算法被第一篇论文广泛引用.
我刚刚成功调整了我在这里找到的开源Hexgrid PathFinding实用程序,以使用PNBA*的串行版本.(实际上在NBA*和PNBA之间的中途*)这将在一两天内上传.
使最短路径更快更简单地概述了使用具有预处理的双向A*开发Bing地图路径查找器.有关预处理工作的详细说明以及相关算法的使用,请参阅Reach for A*和更好的地标范围
