SA*:一种多线程路径规划算法

来源 :地球信息科学学报 | 被引量 : 3次 | 上传用户:gnayief
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法(SA*)。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线
其他文献
针对电力线精细重建问题,该文从分裂导线的空间分布特点出发,提出一种从机载激光点云数据中自动提取并精细重建分裂导线的方法,即在提取单根导线或地线点云的基础上,对分裂导线点云基于二分法提取每根分裂子导线点云,并采用随机抽样一致性算法对电力线分别在XOY平面进行二维直线拟合、在某垂直平面进行悬链线拟合。实验数据表明,该方法具有鲁棒性好、拟合精度高等特点,能精细地重建出每根分裂子导线。
期刊