a算法的改进课程设计毕业设计

课程设计说明书NO1A最短路径算法的改进1课程设计的目的本课程设计是学习数据通信与通信网技术课程必要的教学环节。由于该课程是专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方法，课程设计训练也就成为了一个重要的教学环节。通过对路由算法的设计和实现，达到进一步完善对通信网基础及应用课程学习的效果。2设计方案论证算法具体的形式包括确定起点的最短路径问题即已知起始结点，求最短路径的问题。确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题即已知起点和终点，求两结点之间的最短路径。全局最短路径问题求图中所有的最短路径。（1）FLOYD求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度OV3。FLOYDWARSHALL算法（FLOYDWARSHALLALGORITHM）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。FLOYDWARSHALL算法的时间复杂度为ON3，空间复杂度为ON2。FLOYDWARSHALL的原理是动态规划设DI,J,K为从I到J的只以1K集合中的节点为中间节点的最短路径的长度。若最短路径经过点K，则DI,J,KDI,K,K1DK,J,K1；若最短路径不经过点K，则DI,J,KDI,J,K1。因此，DI,J,KMINDI,K,K1DK,J,K1,DI,J,K1。在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。沈阳大学课程设计说明书NO2FLOYDWARSHALL算法的描述如下FORK1TONDOFORI1TONDOFORJ1TONDOIFDI,KDK,JO（ELGV）。当是稀疏图的情况时，此时EVV/LGV，所以算法的时间复杂度可为O（V2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（VLGVE）。（3）BELLMANFORD求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。BELLMANFORD算法是求解单源最短路径问题的一种算法。单源点的最短路径问题是指给定一个加权有向图G和源点S，对于图G中的任意一点V，求从S到V的最短路径。与DIJKSTRA算法不同的是，在BELLMANFORD算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从V出发，经过若干个点之后又回到V）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。而BELLMANFORD算法具有分辨这种负环路的能力。A（ASTAR算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A算法的数千甚至上万倍。公式表示为FNGNHN,其中FN是从初始点经由节点N到目标点的估价函数，GN是在状态空间中从初始节点到N节点的实际代价，HN是从N到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数HN的选取沈阳大学课程设计说明书NO3估价值HN实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。算法是一种启发式搜索算法,在路径规划中得到广泛的应用,其中启发函数的设计尤其重要。本文针对路径规划问题,对A算法作了以下改进一是在估价函数中考虑以距离和方向两个要素,通过归一化处理解决了单位不统一的问题二是利用KD树空间索引结构,动态加载节点信息,减小内存使用空间。实验结果表明,改进后的A算法的搜索效率得到了明显的提高。最经典的最短路径搜索算法是DIJKSTRA算法,属于遍历搜索,它简单易用并总能搜索到最短路径。但是当网络中节点数较多时,该算法搜索的结点数量会很大,效率非常低。因此有人提出了启发式搜索算法,如局部择优搜索法、最好优先搜索法、A算法等。启发式搜索就是在状态空间中,对每一个搜索的位置进行评估,得到最好的位置,从而在这个位置进行搜索直到搜索到目标为止。目前在路径优化领域,最流行的启发式搜索算法当属由HAR,TNILSSON,RAPHAEL等人首先提出的A算法。它利用启发函数来估计任意点到目标点的远近程度,从而减少搜索空间,提高搜索效率。许多文献都对A算法进行了研究,并且都提出在估价函数中引入距离和方向两个要素。但是距离和方向的单位是不统一的,所以在利用时会出现一些问题,本文针对这一问题进行了研究,并对估价函数进行了改进。另外,为了进一步提高算法的运行效率,本文在算法运行结构上,采用KD树空间索引结构,降低内存存储空间。实验结果证明了改进后算法的合理性和可行性。3设计的过程与分析A算法是建立在DIJKSTRA和BFS最好优先搜索算法基础上的。它的整体框架采用遍历搜索法,但是它采用了启发函数来估计地图上任意点到目标点的费用,从而可以很好地选择搜索方向。A算法引入了当前节点J的启发函数FJ,当前节点J的启发函数定义为FJGJHJ1其中GJ是从起点到当前节点J的实际费用的量度,HJ是从当前节点J到终点的最小费用的估计。沈阳大学课程设计说明书NO4注意到若HJ0,即没有利用任何全局信息,这时A算法就变成了普通的DIJKSTRA算法。因此普通的DIJKSTRA算法可看作A算法的特殊情形。HJ要满足相容性条件即不能高于节点J到终点的实际最小费用。可以证明,如果估价函数满足相容性条件,且原问题存在最优解,则A算法一定能够求出最优路径。A算法的优点在于利用启发函数,使搜索方向更加智能的趋向于终点,所以其搜索深度较小,搜索的节点数少,故占用存储空间少,如图1所示。图1A算法与DIJKSTRA算法搜索区域对比A算法的估价函数A算法的关键在于设计一个合适的启发函数。有文献对其特点进行了分析,认为启发函数FJ值是非递减的,只要能够满足相容性条件即估价函数HJ小于节点J到目标点的实际费用,它生成的路径一定是最优的。许多文献都在估价函数的构造中引入了距离和方向两个要素,即HJW1LW2如图2所示。其中L表示当前节点到终点的欧氏距离,表示起点到当前节点的线段与当前节点到终点的线段的夹角即SJE,有文献也用到了中间节点与关联节点的线段和关联节点与终点的线段夹角NJE。W1和W2分别是距离和角度的加权值,W1和W2的取值范围分别为055065和035045。但距离和角度的单位不统一的问题不能忽略,即使角度的单位为弧度、距离的单位为千米,它们之间也很有可能出现距离值远大于角度值即L的情况,特别是在大区域路径规划过程中,问题更明显。沈阳大学课程设计说明书NO5而当L时,方向不再有约束力,而使得估价函数失去意义。A算法的运行结构当构造合适的估价函数后就要考虑算法的运行,目前大多数方法是将全部数据读入到内存当中,然后搜索最短路径。从理论上讲,A算法可以通过搜索更少的节点完成最短路径的搜索。但是算法运行时,必须要考虑两个问题一是数据读取的速度。即使可以很快地将数据读入到内存中,我们也还要考虑第二个问题,即系统内存的大小。如果系统内存足够大,在算法运行过程中,也将会出现对同一节点进行重复的搜索,从而降低算法的运行效率。针对数据的读取问题,有学者提出了基于限制区域的A算法,减小数据的加载量。但是由于A算法本身就是一种有损算法,这种方法很有可能搜索不到最短路径,特别是在考虑道路属性信息和交通限制信息时。图2估价函数构造示意图改进的A算法（1）A算法估价函数的改进针对A算法估价函数所出现的问题,我们将距离和角度进行归一化处理,即首先计算当前节点所有关联节点相应的距离和角度值,然后求它们的平均值即L，从而使得估价函数变为HJW1LW25其中LL/L6/7归一化处理以后,只考虑距离和角度对路径的贡献,而不必考虑距离和角度的数值大小。从而避免了距离和角度单位不统一的问题。虽然算法的运行要增加计算量,但是我们可以通过进一步减小算法的搜索空间,改善算法的运行结构来提高算法的搜索效率。沈阳大学课程设计说明书NO6针对算法运行效率的问题,建立KD树空间索引结构,动态加载路网数据,从而提高算法效率不失为一个好方法。KD树索引结构是KK1的二叉检索树,主要用于索引多属性的数据或多维点数据,它可以通过坐标快速的访问区域中的路网数据。在算法执行过程中,并非开始就装载所有的路网数据,而是根据算法的需要,读取节点的相关信息,或删除节点信息,虽然会增加运算过程中的I/O运算,但是这样可以避免无效数据的大量装载,占用大量的内存空间。例如,首先判断当前节点是否在确定的范围内,如果不在则装载相应区域的数据,如果在确定的范围内,则读取数据的相关信息,并进行节点扩展。然后,在此基础上计算路段的启发值,搜索最短路径。（2）A算法的实现在算法的实现过程中,要构造两个链表。分别存储待扩展的节点和已扩展的节点,分别称为OPEN表和CLOSE表。算法步骤如下初始化设置。将起点信息加载到OPEN表中,CLOSE表赋值为空。令GJ0。搜索距离当前节点最近的节点,即求FJ的最小值,将节点J从OPEN表中删除并加载到CLOSE表中。判断节点J是否为终点,如果是,终点转向步骤4否则转向步骤3。判断节点J的节点信息是否在确定的范围内,如果在范围内,则扩展节点J否则加载节点J的节点信息并进行扩展。转向步骤2。从节点J开始,利用回溯的方法输出起始节点到目标节点的最优路径,以及最短距离,算法终止。在算法的运行过程中,避免了对同一节点的重复访问,极大地缩小了搜索空间,从而缩短了算法的运行时间。对改进后的A算法进行了实验,在估价函数归一化处理前后的最短路径搜索结果如图3A,B所示。图3A改进前的搜索路径沈阳大学课程设计说明书NO7图3B改进后的搜索路径（3）实验采用郑州市地图,节点2606个,路段4127条,在COREI5,8GB内存的PC机上运行。与其他算法的实验结果进行了对比,结果见表1。表中T表示临时标记节点个数,N表示永久标记节点的个数,D表示规划路径长度。表1算法比较图4临时标记节点个数比较沈阳大学课程设计说明书NO8图5永久标记节点个数比较将表1数据中的临时标记节点,永久标记节点比较关系用图4、图5表示。通过实验由图4可以看出,归一化处理后的A算法的搜索区域明显减小,由表1可以看出A算法的搜索效率要比DIJKSTRA算法的搜索效率高。由图4、图5可知,改进后的A算法的搜索效率明显要高,在利用KD树建立空间索引结构以后,使得搜索的点数明显减少,特别是在区域比较大时,改进后的A算法的效率提高得更加明显。需要指出的是,由于A算法本身就是有损算法,所以其寻找到的路径长度一般要比DIJKSTRA算法的规划结果要长,但由于所选的道路更加合理,所以改进后算法的搜索结果更加实用。4设计体会通过这次的课程设计，利用A算法求解最短路径，加深了对A算法的了解与认识。课程设计环节中把教材里面的理论知识与实践联系起来，利用理论知识指导实践仿真，取得很多的收获。学习这个算法开始的时候会觉得比较难，花了一天的时间看资料理解算法的原理。在知道原理后的第二天开始编写代码，同样也花了一天时间。最后是程序的显示的优化。总之通过学习这个算法编写程序，可以慢慢的从参考别人的代码转变自己知道原理后编写代码这个过程会比较慢需要不断的联系。A算法作为一种启发式搜索算法在路径规划中得到了非常广泛的应用。利用启发函数减小搜索空间,从而提高搜索效率,因此启发函数在A算法中起着关键的作用。针对A算法启发函数中距离和角度两个要素单沈阳大学课程设计说明书NO9位不统一的问题做了研究,提出将距离和角度归一化处理,并且利用KD树的空间索引结构,减少搜索空间。试验结果表明,改进后的A算法的效率明显提高。5参考文献1THCORMEN,CELEISERSON,RLRIVES,TETALINTRODUCTIONTOALGORITHMSMMCGRAWHIL,L20012STEVENMLAVATLEPLANNINGALGORITHMSMCAMBRIDGEUNIVERSITYPRESS,20063李擎，宋顶立两种改进的最优路径规划算法J北京科技大学学报，20114周春辉，李诗高DIJKSTRA算法与A算法研究J软件导刊，20075马进通信网分析M北京人民交通出版社，2003沈阳大学课程设计说明书NO10附录部分程序代码PACKAGECOMUBIRDASTARCOREEXCEPTIONPUBLICCLASSASTARPOSITIONEXCEPTIONEXTENDSRUNTIMEEXCEPTIONPRIVATESTATICFINALLONGSERIALVERSIONUID5968574301453821996LPUBLICASTARPOSITIONEXCEPTIONSTRINGMSGSUPERMSGPACKAGECOMUBIRDASTARCOREIMPORTJAVAUTILARRAYLISTIMPORTJAVAUTILHASHMAPIMPORTJAVAUTILLISTIMPORTJAVAUTILMAPPUBLICCLASSASTARMAPPRIVATELISTOPENLISTNEWARRAYLISTPRIVATEMAPCLOSEMAPNEWHASHMAPPRIVATEBOOLEANISFINDFALSEPRIVATELISTPATHNEWARRAYLISTPUBLICSTATICFINALINTSTATE_BARRIER2ASTARNODETARGETASTARNODESOURCEINTASTARDATAPUBLICASTARMAPINTXGRIDNUM,INTYGRIDNUMTHISASTARDATANEWINTYGRIDNUMXGRIDNUMTHISSOURCENEWASTARNODE0,0THISTARGETNEWASTARNODEXGRIDNUM1,YGRIDNUM1PUBLICASTARNODEGETTARGETRETURNTHISTARGET沈阳大学课程设计说明书NO11PUBLICASTARNODEGETSOURCERETURNTHISSOURCEPUBLICINTGETASTARDATARETURNTHISASTARDATAPUBLICLISTFINDINITASTARNODECURRENTNULLWHILEISENDIFISACHIEVECURRENTBUILDPATHCURRENTTHISISFINDTRUEELSEADD2CLOSEMAPCURRENTFORASTARNODENEIGHBORGETNEIGHBORCURRENTIFNEIGHBORNULL|ISINCLOSEMAPNEIGHBOR|ISCANNOTGOCURRENT,NEIGHBORCONTINUEBOOLEANISBETTERTRUEASTARNODENODEFROMOPENLISTGETNODEFROMOPENLISTNEIGHBORIFNODEFROMOPENLISTNULLNEIGHBORNODEFROMOPENLISTINTTGNEIGHBORDISTINCTGCURRENTISBETTERTG0INDEXIRETURNASTARNODETHISOPENLISTREMOVEINDEXPRIVATEBOOLEANISACHIEVEASTARNODECURRENTRETURNCURRENTEQUALSTHISTARGETPRIVATEVOIDINITINITPARAMETERINITOPENLISTANDCLOSEMAPADDSOURCE2OPENLISTPRIVATEVOIDINITPARAMETERTHISISFINDFALSETHISSOURCEINITTHISTARGETTHISPATHREMOVEALLTHISPATHPRIVATEVOIDINITOPENLISTANDCLOSEMAPCLEAROPENLISTTHISCLOSEMAPCLEARPUBLICVOIDCLEAROPENLISTTHISOPENLISTREMOVEALLTHISOPENLISTPRIVATEVOIDADDSOURCE2OPENLISTADD2OPENLISTTHISSOURCE沈阳大学课程设计说明书NO14PRIVATEVOIDADD2OPENLISTASTARNODENODETHISOPENLISTADDNODEPRIVATEVOIDADD2CLOSEMAPASTARNODENODETHISCLOSEMAPPUTNODETOSTRING,NODEPRIVATEBOOLEANISFINDRETURNTHISISFINDPRIVATEBOOLEANISENDRETURNTHISOPENLISTSIZE0PUBLICVOIDLOADDATAINTDATA,INTBARRIERVAL,INTCLEARVALIFDATANULLRETURNIFDATALENGTHTHISASTARDATALENGTH|THISASTARDATA0LENGTHDATA0LENGTHTHROWNEWRUNTIMEEXCEPTION“NEWDATASHOULDBEASLARGEASTHEOLDASTARMAPDATA“FORINTI0IPRIVATESTATICFINALINTG_110PRIVATESTATICFINALINTG_214PRIVATESTATICFINALINTG_310PRIVATESTATICFINALINTG_414PRIVATESTATICFINALINTG_510PRIVATESTATICFINALINTG_614PRIVATESTATICFINALINTG_710PRIVATESTATICFINALINTG_814PRIVATESTATICFINALINTG_010PRIVATEINTGPRIVATEINTHPRIVATEINTFPRIVATEINTXPRIVATEINTYPRIVATEASTARNODEFATHERPUBLICASTARNODEINTX,INTYTHISXXTHISYYPUBLICINTGETXRETURNTHISXPUBLICVOIDSETXINTXTHISXXPUBLICINTGETYRETURNTHISYPUBLICVOIDSETYINTYTHISYYPUBLICASTARNODEGETFATHERRETURNTHISFATHER沈阳大学课程设计说明书NO16PUBLICVOIDSETFATHERASTARNODEFATHERTHISFATHERFATHERPUBLICVOIDINITASTARNODETARGETTHISG0THISHHEURISTICCOSTESTIMATETHIS,TARGETTHISFTHISGTHISHPUBLICINTHEURISTICCOSTESTIMATEASTARNODESOURCE,ASTARNODETARGETRETURNMATHABSSOURCEXTARGETXMATHABSSOURCEYTARGETY10PUBLICINTCOMPARETOASTARNODEORETURNTHISFOF11PUBLICBOOLEANEQUALSOBJECTOBJIFOBJNULL|OBJINSTANCEOFASTARNODERETURNFALSEASTARNODENODEASTARNODEOBJRETURNNODEXTHISXPUBLICSTRINGTOSTRINGRETURNTHISX“,“THISYPUBLICVOIDRECALCULATORGANDHASTARNODEFATHER,ASTARNODETARGETTHISGDISTINCTGFATHERTHISHHEURISTICCOSTESTIMATETHIS,TARGETTHISFTHISGTHISHTHISFATHERFATHER沈阳大学课程设计说明书NO17PUBLICINTDISTINCTGASTARNODEFATHERINTOFFSETXTHISXFATHERXINTOFFSETYTHISYFATHERYINTDISTINCT0IFOFFSETX0ELSEIFOFFSETX1ELSEIFOFFSETX1ELSEIFOFFSETX1ELSEIFOFFSETX0ELSEIFOFFSETX1ELSEIFOFFSETX1ELSEIFOFFSETX1ELSETHROWNEWASTARPOSITIONEXCEPTION“UNVALIDRELATIONBETWEENCURRENTNODE“THIS“ANDFATERNODE“FATHER“RETURNDISTINCTFATHERGPUBLICINTGETGRETURNTHISGPUBLICBOOLEANISBETTERASTARNODENODERETURNISGBETTERNODEPUBLICBOOLEANISGBETTERASTARNODENODERETURNTHISGDISTINCTGNODENODEG沈阳大学课程设计说明书NO18PUBLICBOOLEANISFBETTERASTARNODENODERETURNTHISFNODEFPUBLICINTGETFRETURNTHISFPACKAGECOMUBIRDASTARDEMOIMPORTCOMUBIRDASTARUIASTARMENUBARIMPORTCOMUBIRDASTARUIASTARPANELIMPORTCOMUBIRDASTARUICONTROLPANELIMPORTCOMUBIRDASTARUISTATUSPANELIMPORTCOMUBIRDASTARUIUFRAMEIMPORTJAVAAWTCONTAINERIMPORTJAVAXSWINGSWINGUTILITIESPUBLICCLASSASTARDEMOPUBLICSTATICVOIDMAINSTRINGARGSSWINGUTILITIESINVOKELATERNEWRUNNABLEPUBLICVOIDRUNUFRAMEFRAMENEWUFRAMEASTARPANELASTARPANELNEWASTARPANEL15,15,60,40STATUSPANELSTATUSPANELNEWSTATUSPANELASTARPANELSETSTATUSPANELSTATUSPANELFRAMEGETCONTENTPANEADDASTARPANEL,“CENTER“FRAMEGETCONTENTPANEADDNEWCONTROLPANELASTARPANEL,“NORTH“FRAMEGETCONTENTPANEADDSTATUSPANEL,“SOUTH“FRAMESETJMENUBARNEWASTARMENUBARASTARPANELFRAMEPACKFRAMESETVISIBLETRUEFRAMESETDEFAULTCLOSEOPERATION3ASTARPANELREQUESTFOCUS沈阳大学课程设计说明书NO19在算法的实现过程中,要构造两个链表。分别存储待扩展的节点和已扩展的节点,分别称为OPEN表和CLOSE表。算法步骤如下1初始化设置。将起点信息加载到OPEN表中,CLOSE表赋值为空。令GJ0。2搜索距离当前节点最近的节点,即求FJ的最小值,将节点J从OPEN表中删除并加载到CLOSE表中。判断节点J是否为终点,如果是,终点转向步骤4否则转向步骤3。3判断节点J的节点信息是否在确定的范围内,如果在范围内,则扩展节点J否则加载节点J的节点信息并进行扩展。转向步骤2。4从节点J开始,利用回溯的方法输出起始节点到目标节点的最优路径,以及最短距离,算法终止。在算法的运行过程中,避免了对同一节点的重复访问,极大地缩小了搜索空间,从而缩短了算法的运行时间。22A算法的实现在算法的实现过程中,要