资源描述：
《a_算法的改进及其在路径规划中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第32卷第6期测绘与空间地理信息Vo.l32,No.62009年12月GEOMATICS&SPATIALINFORMATIONTECHNOLOGYDec.,2009*A算法的改进及其在路径规划中的应用史辉,曹闻,朱述龙,朱宝山(信息工程大学测绘学院,河南郑州450052)*摘要:A算法是一种启发式搜索算法,在路径规划中得到广泛的应用,其中启发函数的设计尤其重要。本文针*对路径规划问题,对A算法作了以下改进:一是在估价函数中考虑以距离和方向两个要素,通过归一化处理解决了单位不统一的问题;二是利用k-d树空间索引结构,动态加载节点信息,减小内存使用空间。实验
2、结果表明,*改进后的A算法的搜索效率得到了明显的提高。*关键词:最短路径;A算法;估价函数;k-d树中图分类号:TP301.6文献标识码:B文章编号:1672-5867(2009)06-0208-04*ApplicationofanImprovedAAlgorithminShortestRoutePlanningSHIHu,iCAOWen,ZHUShu-long,ZHUBao-shan(InstituteofSurveyingandMapping,InformationEngineeringUniversity,Zhengzhou450052,C
3、hina)*Abstract:Aalgorithmasaheuristicalgorithmhasbeenusedwidelyinrouteplanning,inwhichtheheuristicfunctionplaysanimportantpart.Throughtheanalysisofproblemsinrouteplanning,thepapermakessomeimprovementasbellow:oneisthatthecostfunctiontakesthedistanceanddirectionastwoheuristicelement
4、s,andthepapersolvestheproblemthattheyhavedifferentunitbynormalization;anotheristhepaperestablishesank-dtreestructure,loadsthenodeinformationdynamically,andreducesconsumptionofthe*memory.TheexperimentalresultsshowthattheefficiencyofAalgorithmhasbeenimprovedgreatly.*Keywords:shortes
5、troute;Aalgorithm;costfunction;k-dtree了研究,并且都提出在估价函数中引入距离和方向两个0引言要素。但是距离和方向的单位是不统一的,所以在利用最短路径问题是交通网络分析中的重要问题之一。时会出现一些问题,本文针对这一问题进行了研究,并对所谓最短路径,是指在网络G=(V,E,W)或G=(V,A,W)估价函数进行了改进。另外,为了进一步提高算法的运中,找出从起点Vs出发到终点Ve的累计行程最短的路行效率,本文在算法运行结构上,采用k-d树空间索引结径。最短路径搜索算法的要求是速度快,内存占用少,即构,降低内存存储空间。实验
6、结果证明了改进后算法的[1]尽可能降低算法的时间复杂度和空间复杂度。合理性和可行性。最经典的最短路径搜索算法是Dijkstra算法,属于遍*1A算法历搜索,它简单易用并总能搜索到最短路径。但是当网*络中节点数较多时,该算法搜索的结点数量会很大,效率1.1A算法的基本原理[1]*非常低。因此有人提出了启发式搜索算法,如:局部择A算法是建立在Dijkstra和BFS(最好优先搜索)算*优搜索法、最好优先搜索法、A算法等。启发式搜索就是法基础上的。它的整体框架采用遍历搜索法,但是它采在状态空间中,对每一个搜索的位置进行评估,得到最好用了启发函数来估计地图上任意
7、点到目标点的费用,从*的位置,从而在这个位置进行搜索直到搜索到目标为止。而可以很好地选择搜索方向。A算法引入了当前节点j*目前在路径优化领域,最流行的启发式搜索算法当属由的启发函数f(j),当前节点j的启发函数定义为:***Har,tNilsson,Raphael等人首先提出的A算法。它利用f(j)=g(j)+h(j)(1)启发函数来估计任意点到目标点的远近程度,从而减少其中g(j)是从起点到当前节点j的实际费用的量度,[2]**搜索空间,提高搜索效率。许多文献都对A算法进行h(j)是从当前节点j到终点的最小费用的估计。注意到收稿日期:2009-03-1
8、8作者简介:史辉(1984-),男,河北保定人,在
