本文已被:浏览 1695次 下载 2810次
Received:October 20, 2017 Revised:November 21, 2017
Received:October 20, 2017 Revised:November 21, 2017
中文摘要: 在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.
Abstract:In the field of NPC game or GIS system development, there are more studies on finding the efficient method of the shortest path search problem, especially the research of A* algorithm efficiency optimization in the search of finding shortest path algorithm. Most of the maps used in artificial intelligence or algorithm research are based on arbitrary graphs rather than grid-based graphs. Based on above mentioned scenario, by combining arbitrary graphs with grid graphs and directions, an optimization of A* algorithm is proposed in this study. The heuristic search strategy is improved, which can reduce the scale and range of algorithm search and improve the efficiency of A* algorithm. Finally, the experimental results show that compared with the traditional A* algorithm, after the optimization of A* algorithm, the heuristic search strategy is more accurate and the computational efficiency became more efficient and more quickly.
文章编号: 中图分类号: 文献标志码:
基金项目:韶关学院大学生创新创业训练计划立项项目(国家级)(201710576001);韶关学院第十六批教育教学改革研究一般项目(SYJY20151623)
引用文本:
梁昭阳,蓝茂俊,陈正铭.A*算法在Shortest-Path方面的优化研究.计算机系统应用,2018,27(7):255-259
LIANG Zhao-Yang,LAN Mao-Jun,CHEN Zheng-Ming.Optimization of A* Algorithm in Finding Shortest-Path.COMPUTER SYSTEMS APPLICATIONS,2018,27(7):255-259
梁昭阳,蓝茂俊,陈正铭.A*算法在Shortest-Path方面的优化研究.计算机系统应用,2018,27(7):255-259
LIANG Zhao-Yang,LAN Mao-Jun,CHEN Zheng-Ming.Optimization of A* Algorithm in Finding Shortest-Path.COMPUTER SYSTEMS APPLICATIONS,2018,27(7):255-259