[1]朱云虹,袁一.基于改进A*算法的最优路径搜索[J].计算机技术与发展,2018,28(04):55-59.[doi:10.3969/ j. issn.1673-629X.2018.04.012]
　ZHU Yun-hong,YUAN Yi.Optimal Path Search Based on Improved A* Algorithm[J].,2018,28(04):55-59.[doi:10.3969/ j. issn.1673-629X.2018.04.012]
点击复制

基于改进A*算法的最优路径搜索()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
28
期数:
2018年04期
页码:
55-59
栏目:
智能、算法、系统工程
出版日期:
2018-04-10

文章信息/Info

Title:
Optimal Path Search Based on Improved A* Algorithm
文章编号:
1673-629X(2018)04-0055-05
作者:
朱云虹1 ; 袁一2
1. 南京邮电大学 通信与信息工程学院,江苏 南京 210003;
2. 南京大学 地理与海洋科学学院,江苏 南京 210093
Author(s):
ZHU Yun-hong1 ; YUAN Yi2
1. School of Communication and Information Engineering,Nanjing University of osts and Telecommunications,Nanjing 210003,China；
2. School of Geography and Marine Sciences,Nanjing University,Nanjing 210093,China
关键词:
A*算法;  最优路径;  启发式函数;  规避交通
Keywords:
A* algorithm; shortest path; heuristic function; avoidance of traffic light
分类号:
TP301.6
DOI:
10.3969/ j. issn.1673-629X.2018.04.012
文献标志码:
A
摘要:
最短路径搜索问题是智能交通技术应用中的一个关键问题,而A*算法是一种静态路网中求解最短路径最有效的直接搜索方法.传统的A*算法未考虑到实际路网中交通灯的影响,求得的最短路径并不一定是行程时间最短.但是路径选取在实际应用中主要追求最优而不是最短,因此传统的A*算法有一定的局限性.为了克服以上问题,通过将交通灯的等待时间引入启发式函数,构造一种新的启发式函数并应用于A*算法,利用减少最短路径搜索中路网上等待交通灯的时间来优化路径的总行程时间.通过对Minneapolis的地图基础数据进行路径搜索实验,结果表明,改进的A*算法有助于降低最短路径的总行程时间成本,并且与传统的A*算法搜索消耗的时间效率相似.
Abstract:
The shortest path search is still a key problem in the application of intelligent transportation technology,and the A* algorithm is the most effective search method to solve the shortest path problems in a static road network. However,the selections of paths in the practical applications mainly pursue the best rather than the shortest,and the traditional A* algorithm does not deal with traffic lights in the actual conditions. Therefore,there are some limitations of the traditional A* algorithm. For example,the shortest path is not necessarily the shortest travel time. In response to these problems,by introducing the heuristic function into the waiting time of the traffic lights,we propose a new heuristic function into the traditional A* algorithm to reduce the time of waiting for traffic lights on the shortest path search. The experiments of path search on basic map data of Minneapolis show that the improved A* algorithm helps to reduce the total time cost of the shortest path and is similar to the time efficiency of the traditional A* algorithm.

相似文献/References:

[1]郑延斌 李新源 段德全.一种保持Agent团队队形的路径规划方法[J].计算机技术与发展,2009,(07):159.
　ZHENG Yan-bin,LI Xin-yuan,DUAN De-quan.A Path Planning Algorithm with Agent Team Formation Maintained[J].,2009,(04):159.
[2]冯晓辉 马光思.数码谜题求解的算法设计及其扩展研究[J].计算机技术与发展,2009,(08):110.
　FENG Xiao-hui,MA Guang-si.Algorithm Design and Extension Research of N - Puzzle Problem[J].,2009,(04):110.
[3]李培 何中市.基于ArcGIS和GPS的水电气管理系统设计与实现[J].计算机技术与发展,2009,(01):172.
　LI Pei,HE Zhong-shi.Design and Implementation Water, Electricity and Gas Management System Based on ArcGIS and GPS[J].,2009,(04):172.
[4]朱永红 张燕平.用VC＋＋实现基于A＊算法的八数码问题[J].计算机技术与发展,2006,(09):32.
　ZHU Yong-hong,ZHANG Yan-ping.Programming for Eight - Figure Puzzle Problem Based on Algorithm A ＊ with Visual C ＋ ＋[J].,2006,(04):32.
[5]陈益富 卢潇 丁豪杰.对Dijkstra算法的优化策略研究[J].计算机技术与发展,2006,(09):73.
　CHEN Yi-fu,LU Xiao,DING Hao-jie.Optimized Strategy Research over Algorithm of Dijkstra[J].,2006,(04):73.
[6]方伟华.基于A＊算法和图遍历的烟草物流VRP的研究[J].计算机技术与发展,2011,(12):63.
　FANG Wei-hua.Research on Tobacco Logistics VRP Based on A ＊ Algorithm and Graph Traversal[J].,2011,(04):63.
[7]刘钰 陆建峰 蔡海舟.基于改进A＊算法的机器人路径规划方法研究[J].计算机技术与发展,2012,(12):108.
　LIU Yu,LU Jian-feng,CAI Hai-zhou.Research on Path Planning Method of Robot Based on Improved A ＊ Algorithm[J].,2012,(04):108.
[8]马静,王佳斌,张雪. A*算法在无人车路径规划中的应用[J].计算机技术与发展,2016,26(11):153.
　MA Jing,WANG Jia-bin,ZHANG Xue. Application of A* Algorithm in Unmanned Vehicle Path Planning[J].,2016,26(04):153.
[9]程 杰,陈姚节.基于正六边形建模的无人水面艇路径规划[J].计算机技术与发展,2020,30(11):37.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 007]
　CHENG Jie,CHEN Yao-jie.Path Planning of Unmanned Surface Vehicle Based on Regular Hexagon Modeling[J].,2020,30(04):37.[doi:10. 3969 / j. issn. 1673-629X. 2020. 11. 007]
[10]叶小艳,钟华钧,邓可儿.一种基于改进 A*算法的室内导航路径规划方法[J].计算机技术与发展,2022,32(02):202.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 033]
　YE Xiao-yan,ZHONG Hua-jun,DENG Ke-er.A Path Planning Method of Indoor Navigation Based on Improved A-Star Algorithm[J].,2022,32(04):202.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 033]

更新日期/Last Update: 2018-06-06