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

• 作者: 周英华 孙广中 孙经纬 毛睿 詹石岩
• 来源期刊: 地球信息科学学报
• 关键词: 多线程 并行计算 路径规划 启发式搜索
• 年，卷（期）: 2018,（6）
• 所属期刊栏目: 2017年中国地理信息科学理论与方法学术年会优秀论文专辑
• 页码范围: 753-761
• 页数: 9页
• 语种: 中文

摘要

路径规划问题是路网交通应用中的一个基础问题.A算法是一个求解点到点最短路径问题的高效算法.但随着路网数据规模的增长,A难以保证求解的实时性.利用并行计算进行加速是常用的算法性能提高手段,然而A算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化.本文提出一种分段化搜索的改进A算法(SA).该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解.分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度.实验结果表明,在真实路网数据上,利用16核的机器,SA的性能可以达到A算法的10-30倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙广中	中国科学技术大学计算机科学与技术学院	34	328	8.0	17.0
2	周英华	中国科学技术大学计算机科学与技术学院	6	21	3.0	4.0
3	毛睿	深圳大学计算机与软件学院	18	81	5.0	8.0
4	孙经纬	中国科学技术大学计算机科学与技术学院	1	2	1.0	1.0
5	詹石岩	中国科学技术大学计算机科学与技术学院	1	2	1.0	1.0