| 基于打破对称性的快速寻路算法 |
| |
| 引用本文： | 邱磊.基于打破对称性的快速寻路算法[J].宁夏大学学报(自然科学版),2014(3):216-220. |
| |
| 作者姓名： | 邱磊 |
| |
| 作者单位： | 武汉船舶职业技术学院 电气与电子工程学院,湖北 武汉,430050 |
| |
| 基金项目： | 湖北省教育厅科学技术研究计划指导性项目，湖北自然科学基金面上项目 |
| |
| 摘 要： | 基于Java实现了跳点搜索算法,给出了算法实现的过程.实验结果表明:跳点搜索算法找到了一条从起始节点到目标节点的最优路径,且能够有效地识别和消除网格地图上的路径对称性,大幅度减少了节点扩展的数量.对比A*、宽度优先搜索、最佳优先搜索和Dijkstra可知,在所求解的路径长度一致的情况下,跳点搜索在平均搜索时间上显著快于其他算法.因此,跳点搜索是快速、高效的.
|
| 关 键 词： | 网格地图 寻路 跳点搜索 路径的对称性 |
Fast Pathfinding Algorithm Based on Breaking Symmetry |
| |
| QiuLei.Fast Pathfinding Algorithm Based on Breaking Symmetry[J].Journal of Ningxia University(Natural Science Edition),2014(3):216-220. |
| |
| Authors: | QiuLei |
| |
| Institution: | QiuLei (College of Electrical and Electronic Engineering, Wuhan Institute of Shipbuilding Technology, Wuhan 430050, China) |
| |
| Abstract: | Jump Point Search （JPS）algorithm is implemented in Java,and the implementation procedures of JPS algorithm is given.Experimental results show that an optimal path has been found by JPS algorithm from start node to goal node,which could identify and eliminate path symmetries on grid maps effectively, so it reduces nodes number expanded by a large margin.Comparing JPS with A＊,Breadth First Search, Best First Search and Dijkstra,the results show that JPS is faster over them more pronounced on condition of the path length being computed are uniform.For these reasons,JPS algorithm is fast and effective. |
| |
| Keywords: | grid map pathfinding j ump point search path symmetry |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
