一种基于A<sup>*</sup>算法改进的最短路径搜索方法

魏为民; 陆致静; 叶语亭

###

DOI:10.3969/j.issn.1006-4729.2018.02.016

上海电力大学学报:2018,34(2):180-184

查看/发表评论过刊浏览高级检索 HTML

←前一篇 | 后一篇→

码上扫一扫！

下载全文

一种基于A^*算法改进的最短路径搜索方法

魏为民¹, 陆致静¹, 叶语亭²

(1.上海电力学院计算机科学与技术学院;2.中国计量大学机电工程学院)

Improvement and Contrast Analysis of Variants of A^* Algorithm

WEI Weimin¹, LU Zhijing¹, YE Yuting²

(1.School of Computer Science and Technology, Shanghai University of Electric Power, Shanghai 200090, China;2.College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China)

摘要

图/表

参考文献

本刊相似文献

All Journals 相似文献

All Journals 引证文献

本文已被：浏览 1368次下载 662次
投稿时间：2017-03-09

中文摘要: 无论是城市交通导航还是游戏人物导航，最短路径的有效搜索都是人们最为关注的部分。A^*算法是目前在导航方面较为有效的最短路径算法。对传统的A^*算法，A_ε算法，AlphaA^*算法以及添加启发式算法进行了对比分析，提出了一种改进方法A^*+算法，即在原有算式上添加父节点启发式，并计算临界值筛选候选节点。实验结果表明，该方法节点排查能力明显优化，搜索效率得到提高。

中文关键词: A^*算法 A_ε算法 AlphaA^*算法 A^*+算法添加启发式算法最短路径

Abstract: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.

keywords: A^* algorithm A_ε algorithm Alpha A^* algorithm A^*+ algorithm new heuristic algorithm shortest path

文章编号：20182016 中图分类号： 文献标志码：

基金项目:上海市自然科学基金（15ZR1418500）；上海市科学技术委员会地方院校能力建设项目（15110500700）。

作者	单位	E-mail
魏为民	上海电力学院计算机科学与技术学院	wwm@shiep.edu.cn
陆致静	上海电力学院计算机科学与技术学院
叶语亭	中国计量大学机电工程学院

Author Name	Affiliation	E-mail
WEI Weimin	School of Computer Science and Technology, Shanghai University of Electric Power, Shanghai 200090, China	wwm@shiep.edu.cn
LU Zhijing	School of Computer Science and Technology, Shanghai University of Electric Power, Shanghai 200090, China
YE Yuting	College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China

引用文本：
魏为民,陆致静,叶语亭.一种基于A^*算法改进的最短路径搜索方法[J].上海电力大学学报,2018,34(2):180-184.
WEI Weimin,LU Zhijing,YE Yuting.Improvement and Contrast Analysis of Variants of A^* Algorithm[J].Journal of Shanghai University of Electric Power,2018,34(2):180-184.