摘要
无论是城市交通导航还是游戏人物导航,最短路径的有效搜索都是人们最为关注的部分。A~*算法是目前在导航方面较为有效的最短路径算法。对传统的A~*算法,A_ε算法,Alpha A~*算法以及添加启发式算法进行了对比分析,提出了一种改进方法 A^(*+)算法,即在原有算式上添加父节点启发式,并计算临界值筛选候选节点。实验结果表明,该方法节点排查能力明显优化,搜索效率得到提高。
Whether in the traffic navigation or game path-navigation field,the efficiency of searching shortest paths is one that receives most concern.Now A*algorithm is a more efficient shortest path algorithm in the navigation field.Through the comparison and analysis of the varieties based on A*algorithm-Aε,AlphaA*and new heuristic algorithm,an improved method,A*+is put forward,namely,adding a new heuristic in the original formula and calculating the threshold to filter candidate nodes.
作者
魏为民
陆致静
叶语亭
WEI Weimin;LU Zhijing;YE Yuting(School of Computer Science and Technology,Shanghai University of Electric Power,Shanghai 200090,China;College of Mechanical and Electrical Engineering,China Jiliang University,Hangzhou 310018,China)
出处
《上海电力学院学报》
CAS
2018年第2期180-184,共5页
Journal of Shanghai University of Electric Power
基金
上海市自然科学基金(15ZR1418500)
上海市科学技术委员会地方院校能力建设项目(15110500700)
