面向多值栅格地图的A~*最优路径算法改进  

Improvement of A~* Optimal Path Algorithm for Multi-Valued Raster Map

作　　者：邓圣乾 李宏伟[1] 赵家瑶 姜晶莉 DENG Shengqian;LI Hongwei;ZHAO Jiayao;JIANG Jingli(Information Engineering University, Zhengzhou 450001, China)

机构地区：[1]信息工程大学

出　　处：《测绘科学技术学报》2019年第2期202-208,共7页Journal of Geomatics Science and Technology

基　　金：国家自然科学基金项目(41571394)

摘　　要：A*启发算法是最优路径规划问题中最有效的算法之一,在路径规划问题中得到广泛应用。针对多值栅格环境下的最优路径规划的效率问题,对A*算法在搜索策略上做了如下改进:一是提出了两种新的启发函数;二是提出了新的A*双向搜索算法。实验表明改进算法求得的路径为最优路径,搜索效率比传统的Dijkstra算法有显著提升,双向A*算法比单向A*算法效率有明显提高。A * heuristic algorithm is one of the most effective algorithms in the optimal path planning problem, so it is widely used in the path planning problem. For improving the efficiency of optimal path planning in multi-valued grid environment, the search strategy of A * algorithm is improved in the paper as follows. Firstly, two new heuristic functions are proposed. Secondly, a new A * bidirectional search algorithm is proposed. Experiments show that the path obtained by the improved algorithm is the optimal path, and the search efficiency is remarkably improved compared with the traditional Dijkstra algorithm. The efficiency of the bidirectional A * algorithm is obviously improved compared with the unidirectional A * algorithm.

关 键 词：A*最优路径算法 算法改进 多值栅格 启发函数 双向搜索 

分 类 号：P208[天文地球—地图制图学与地理信息工程]