地球信息科学学报 ›› 2018, Vol. 20 ›› Issue (6): 753-761.doi: 10.12082/dqxxkx.2018.180019
• 2017年中国地理信息科学理论与方法学术年会优秀论文专辑 • 上一篇 下一篇
孙经纬1(), 孙广中1, 詹石岩1, 毛睿2, 周英华1,*(
)
收稿日期:
2018-01-02
修回日期:
2018-03-10
出版日期:
2018-06-20
发布日期:
2018-06-20
通讯作者:
周英华
E-mail:sunjw@mail.ustc.edu.cn;yinghua@ustc.edu.cn
作者简介:
作者简介:孙经纬(1992-),男,博士生,主要从事高性能计算与算法优化研究。E-mail:
基金资助:
SUN Jingwei1(), SUN Guangzhong1, ZHAN Shiyan1, MAO Rui2, ZHOU Yinghua1(
)
Received:
2018-01-02
Revised:
2018-03-10
Online:
2018-06-20
Published:
2018-06-20
Supported by:
摘要:
路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法(SA*)。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。
孙经纬, 孙广中, 詹石岩, 毛睿, 周英华. SA*:一种多线程路径规划算法[J]. 地球信息科学学报, 2018, 20(6): 753-761.DOI:10.12082/dqxxkx.2018.180019
SUN Jingwei,SUN Guangzhong,ZHAN Shiyan,MAO Rui,ZHOU Yinghua. SA*: A Multi-thread Path Routing Algorithm[J]. Journal of Geo-information Science, 2018, 20(6): 753-761.DOI:10.12082/dqxxkx.2018.180019
表3
不同方法的平均相对误差(%)"
方法 | 分段 | NW | NE | CAL | E | W | USA |
---|---|---|---|---|---|---|---|
SA*(line) | k=2 | 6.5 | 6.4 | 6.5 | 4.5 | 5.1 | 1.9 |
k=4 | 17.0 | 13.3 | 17.0 | 12.2 | 13.4 | 5.5 | |
k=8 | 36.5 | 26.2 | 36.5 | 23.1 | 30.1 | 12.5 | |
k=16 | 66.8 | 49.1 | 66.7 | 45.5 | 61.2 | 33.1 | |
SA*(path) | k=2 | 3.2 | 1.4 | 3.1 | 1.7 | 2.5 | 1.8 |
k=4 | 5.8 | 3.3 | 5.8 | 3.6 | 4.7 | 3.4 | |
k=8 | 7.7 | 5.2 | 8.2 | 5.5 | 6.9 | 5.3 | |
k=16 | 9.4 | 7.1 | 10.1 | 7.4 | 8.8 | 7.1 |
[1] |
Dijkstra E W.A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959,1(1):269-271.
doi: 10.1007/BF01386390 |
[2] | Bellman R.On a routing problem[J]. Quarterly of applied mathematics, 1958:87-90. |
[3] |
Cherkassky B V, Goldberg A V, Radzik T.Shortest paths algorithms: Theory and experimental evaluation[J]. Mathematical programming, 1996,73(2):129-174.
doi: 10.1007/BF02592101 |
[4] |
Hart P E, Nilsson N J, Raphael B.A formal basis for the heuristic determination of minimum cost paths[J]. IEEE transactions on Systems Science and Cybernetics, 1968,4(2):100-107.
doi: 10.1109/TSSC.1968.300136 |
[5] | Pohl I.Bi-directional and heuristic search in path problems[D]. Stanford: Stanford University, 1969. |
[6] | Ikeda T, Hsu M Y, Imai H, et al.A fast algorithm for finding better routes by AI search techniques[C]. Vehicle Navigation and Information Systems Conference, 1994:291-296. |
[7] | Brand S.Efficient obstacle avoidance using autonomously generated navigation meshes[D]. TU Delft, Delft University of Technology, 2009. |
[8] | Brand S, Bidarra R.Parallel ripple search-scalable and efficient pathfinding for multi-core architectures[C]. International Conference on Motion in Games. Springer Berlin Heidelberg, 2011:290-303. |
[9] | Pearl J.Heuristics: Intelligent search strategies for computer problem solving[M]. Boston: Addison-Wesley Longman Publishing Company, 1984. |
[10] | Demetrescu C, Goldberg A V, Johnson D S.The shortest path problem: Ninth DIMACS implementation challenge[M]. American Mathematical Soc, 2009. |
[11] | Camil D, Andrew G, David J. 9th dimacs implementation challenge - shortest paths[EB/OL]. , 2009-10-21 |
[12] | Ratner D, Pohl I.Joint and LPA*: combination of approximation and search[C]. Proceedings of the Fifth AAAI National Conference on Artificial Intelligence. AAAI Press, 1986:173-177. |
[13] |
Korf R E.Depth-first iterative-deepening: An optimal admissible tree search[J]. Artificial intelligence, 1985,27(1):97-109.
doi: 10.1016/0004-3702(85)90084-0 |
[14] | Björnsson Y, Enzenberger M, Holte R C, et al.Fringe Search: Beating A* at Pathfinding on Game Maps[J]. CIG, 2005,5:125-132. |
[15] | Goldberg A V, Harrelson C.Computing the shortest path: A search meets graph theory[C]. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005:156-165. |
[16] | Andrew G, Renato W.Computing Point-to-Point Shortest Paths from External Memory[C]. Proceedings of the seventh International Workshop on Algorithm Engineering and Experiments, 2005. SIAM, 2005:26-40. |
[17] | Geisberger R, Sanders P, Schultes D, et al.Contraction hierarchies: Faster and simpler hierarchical routing in road networks[C]. International Workshop on Experimental and Efficient Algorithms. Springer Berlin Heidelberg, 2008:319-333. |
[18] | Arz J, Luxen D, Sanders P.Transit node routing reconsidered[C]. International Symposium on Experimental Algorithms. Springer Berlin Heidelberg, 2013:55-66. |
[19] |
Delling D, Goldberg A V, Nowatzyk A, et al.Phast: Hardware-accelerated shortest path trees[J]. Journal of Parallel and Distributed Computing, 2013,73(7):940-952.
doi: 10.1016/j.jpdc.2012.02.007 |
[20] | Abraham I, Delling D, Goldberg A V, et al.A hub-based labeling algorithm for shortest paths in road networks[C]. International Symposium on Experimental Algorithms. Springer Berlin Heidelberg, 2011:230-241. |
[21] | Botea A, Baier J A, Harabor D, et al.Moving target search with compressed path databases[C]. Proceedings of the Twenty-Third International Conference on International Conference on Automated Planning and Scheduling. AAAI Press, 2013:288-292. |
[22] | Sankaranarayanan J, Alborzi H, Samet H.Efficient query processing on spatial networks[C]. Proceedings of the 13th annual ACM international workshop on Geographic information systems. ACM, 2005:200-209. |
[23] |
Sankaranarayanan J, Samet H, Alborzi H.Path oracles for spatial networks[J]. Proceedings of the VLDB Endowment, 2009,2(1):1210-1221.
doi: 10.14778/1687627.1687763 |
[24] |
Sun J, Sun G.SPLZ: An efficient algorithm for single source shortest path problem using compression method[J]. GeoInformatica, 2016,20(1):1-18.
doi: 10.1007/s10707-015-0229-7 |
[25] |
陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报,2000,25(3):226-232.
doi: 10.3321/j.issn:1671-8860.2000.03.008 |
[ Lu F, Zhou C H, Wan Q.An optimum vehicular path algorithm for traffic network base on hierarchical spatial reasoning[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000,25(3):226-232.
doi: 10.3321/j.issn:1671-8860.2000.03.008 |
|
[26] |
李清泉,郑年波,徐敬海,等.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报,2007,12(7):1280-1285.
doi: 10.3969/j.issn.1006-8961.2007.07.024 |
[ Li Q Q, Zheng N B, Xu J H, et al.A hierarchical route planning algorithm based on multi-level topological structure of road network[J]. Journal of Image and Graphics, 2007,12(7):1280-1285. ]
doi: 10.3969/j.issn.1006-8961.2007.07.024 |
|
[27] | 高松,陆锋.一种基于路网等级启发式策略的路径搜索算法[J].地球信息科学学报,2009,11(2):151-156. |
[ Gao S, Lu F.A path finding heuristic algorithm for a road network hierarchy[J]. Journal of Geo-information Science, 2009,11(2):151-156. ] | |
[28] |
刘康,段滢滢,张恒才.基于路网拓扑层次性表达的驾车路径规划方法[J].地球信息科学学报,2015,17(9):1039-1046.
doi: 10.3724/SP.J.1047.2015.01039 |
[ Liu K, Duan Y Y, Zhang He C.A driving route planning method based on road network topological hierarchy expression[J]. Journal of Geo-information Science, 2015,17(9):1039-1046. ]
doi: 10.3724/SP.J.1047.2015.01039 |
|
[29] |
Meyer U, Sanders P.Δ-stepping: a parallelizable shortest path algorithm[J]. Journal of Algorithms, 2003,49(1):114-152.
doi: 10.1016/S0196-6774(03)00076-2 |
[30] | Madduri K, Bader D A, Berry J W, et al.Parallel Shortest Path Algorithms for Solving Large-Scale Instances[R]. Georgia Institute of Technology, 2006. |
[1] | 秦承志. 数字地形分析方法研究的维度——精准、高效、易用[J]. 地球信息科学学报, 2020, 22(4): 720-730. |
[2] | 王浩, 王含宇, 杨名宇, 许永森. Retinex图像增强在GPU平台上的实现[J]. 地球信息科学学报, 2019, 21(4): 623-629. |
[3] | 潘淼鑫, 林甲祥, 陈崇成, 叶晓燕. 基于C-SOM和Spark的并行空间离群挖掘方法及应用[J]. 地球信息科学学报, 2019, 21(1): 128-136. |
[4] | 邱强, 秦承志, 朱效民, 赵晓芳, 方金云. 全空间下并行矢量空间分析研究综述与展望[J]. 地球信息科学学报, 2017, 19(9): 1217-1227. |
[5] | 周恩波, 毛善君, 李梅, 孙振明. GPU加速的改进PAM聚类算法研究与应用[J]. 地球信息科学学报, 2017, 19(6): 782-791. |
[6] | 刘洋, 关庆锋. 景观指数的并行计算方法[J]. 地球信息科学学报, 2017, 19(4): 457-466. |
[7] | 江岭, 王春, 赵明伟, 杨灿灿. 面向数据传输的地理栅格数据快速压缩方法[J]. 地球信息科学学报, 2016, 18(7): 894-901. |
[8] | 沈占锋, 李均力, 于新菊. 基于协同计算的白洋淀湿地时序水体信息提取[J]. 地球信息科学学报, 2016, 18(5): 690-698. |
[9] | 李梦雅, 王军, 沈航. 洪灾应急疏散路径规划算法优化[J]. 地球信息科学学报, 2016, 18(3): 362-368. |
[10] | 刘康, 段滢滢, 张恒才. 基于路网拓扑层次性表达的驾车路径规划方法[J]. 地球信息科学学报, 2015, 17(9): 1039-1046. |
[11] | 刘扬, 付征叶, 郑逢斌. 高分辨率遥感影像目标分类与识别研究进展[J]. 地球信息科学学报, 2015, 17(9): 1080-1091. |
[12] | 王春, 江岭, 陈泰生, 杨灿灿. 基于Pfafstetter规则的流域编码算法并行化方法[J]. 地球信息科学学报, 2015, 17(5): 556-561. |
[13] | 刘军志, 朱阿兴, 秦承志, 江净超, 朱良君, 沈琳. 论地理规律对流域过程模拟并行计算的指导作用[J]. 地球信息科学学报, 2015, 17(5): 506-514. |
[14] | 任沂斌, 陈振杰, 程亮, 李满春, 骈宇哲. 采用动态负载均衡的LiDAR数据生成DEM并行算法[J]. 地球信息科学学报, 2015, 17(5): 531-537. |
[15] | 艾贝贝, 秦承志, 朱阿兴. 栅格地理计算并行算子对区域计算算法并行化的可用性分析——以多流向算法为例[J]. 地球信息科学学报, 2015, 17(5): 562-567. |
|