-
题名SA*:一种多线程路径规划算法
被引量：2
- 1
-
-
作者
孙经纬
孙广中
詹石岩
毛睿
周英华
-
机构
中国科学技术大学计算机科学与技术学院
深圳大学计算机与软件学院
-
出处
《地球信息科学学报》
CSCD
北大核心
2018年第6期753-761,共9页
-
基金
国家自然科学基金项目(61432016
61303047)
+1 种基金
广东省普通高校国家级重大培育项目(2014GKXM054)
广东省普及型高性能计算机重点实验室(2017B030314073)~~
-
文摘
路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法(SA*)。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。
-
关键词
多线程
并行计算
路径规划
启发式搜索
-
Keywords
multi-thread
parallel computing
path routing
heuristic search
road network
-
分类号
U491
[交通运输工程—交通运输规划与管理]
-
