A*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中，专门针对最短路径搜索方面的优化研究较多，尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况，通过任意图与网格图及方向的相结合，提出了三种优化A*算法的启发式函数搜索策略，较好地减小了算法搜索的范围和规模，有效地提高了A*算法的运行效率.最后的实验结果显示，与传统的A*算法相比较，优化启发搜索策略后的A*算法寻径更快速，更准确，计算效率更高.

Optimization of A* Algorithm in Finding Shortest-Path

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.