A算法的改进课程设计

课程设计说明书NO.1A*最短路径算法的改进1.课程设计的目的本课程设计是学习《数据通信与通信网技术》课程必要的教学环节。由于该课程是专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方法，课程设计训练也就成为了一个重要的教学环节。通过对路由算法的设计和实现，达到进一步完善对通信网基础及应用课程学习的效果。2.设计方案论证算法具体的形式包括：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。全局最短路径问题：求图中所有的最短路径。（1）Floyd求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。Floyd-Warshall算法（Floyd-Warshallalgorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。Floyd-Warshall的原理是动态规划：设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。若最短路径经过点k，则Di,j,k=Di,k,k-1+Dk,j,k-1；若最短路径不经过点k，则Di,j,k=Di,j,k-1。因此，Di,j,k=min(Di,k,k-1+Dk,j,k-1,Di,j,k-1)。在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。沈阳大学课程设计说明书NO2Floyd-Warshall算法的描述如下：fork←1tondofori←1tondoforj←1tondoif(Di,k+Dk,jDi,j)thenDi,j←Di,k+Dk,j;其中Di,j表示由点i到点j的代价，当Di,j为∞表示两点之间没有任何连接。（2）Dijkstra求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV+E）。（3）Bellman-Ford求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。Bellman-Ford算法是求解单源最短路径问题的一种算法。单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。而Bellman-Ford算法具有分辨这种负环路的能力。A*（A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。注意是最有效的直接搜索算法。之后涌现了很多预处理算法（ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。公式表示为：f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：沈阳大学课程设计说明书NO.3估价值h(n)=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行，此时的搜索效率是最高的。如果估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。算法是一种启发式搜索算法,在路径规划中得到广泛的应用,其中启发函数的设计尤其重要。本文针对路径规划问题,对A*算法作了以下改进:一是在估价函数中考虑以距离和方向两个要素,通过归一化处理解决了单位不统一的问题;二是利用k-d树空间索引结构,动态加载节点信息,减小内存使用空间。实验结果表明,改进后的A*算法的搜索效率得到了明显的提高。最经典的最短路径搜索算法是Dijkstra算法,属于遍历搜索,它简单易用并总能搜索到最短路径。但是当网络中节点数较多时,该算法搜索的结点数量会很大,效率非常低。因此有人提出了启发式搜索算法,如:局部择优搜索法、最好优先搜索法、A*算法等。启发式搜索就是在状态空间中,对每一个搜索的位置进行评估,得到最好的位置,从而在这个位置进行搜索直到搜索到目标为止。目前在路径优化领域,最流行的启发式搜索算法当属由Har,tNilsson,Raphael等人首先提出的A*算法。它利用启发函数来估计任意点到目标点的远近程度,从而减少搜索空间,提高搜索效率。许多文献都对A*算法进行了研究,并且都提出在估价函数中引入距离和方向两个要素。但是距离和方向的单位是不统一的,所以在利用时会出现一些问题,本文针对这一问题进行了研究,并对估价函数进行了改进。另外,为了进一步提高算法的运行效率,本文在算法运行结构上,采用k-d树空间索引结构,降低内存存储空间。实验结果证明了改进后算法的合理性和可行性。3.设计的过程与分析A*算法是建立在Dijkstra和BFS(最好优先搜索)算法基础上的。它的整体框架采用遍历搜索法,但是它采用了启发函数来估计地图上任意点到目标点的费用,从而可以很好地选择搜索方向。A*算法引入了当前节点j的启发函数f*(j),当前节点j的启发函数定义为:f*(j)=g(j)+h*(j)(1)其中g(j)是从起点到当前节点j的实际费用的量度,h*(j)是从当前节点j到终点的最小费用的估计。沈阳大学课程设计说明书NO.4注意到若h*(j)=0,即没有利用任何全局信息,这时A*算法就变成了普通的Dijkstra算法。因此普通的Dijkstra算法可看作A*算法的特殊情形。h*(j)要满足相容性条件:即不能高于节点j到终点的实际最小费用。可以证明,如果估价函数满足相容性条件,且原问题存在最优解,则A*算法一定能够求出最优路径。A*算法的优点在于利用启发函数,使搜索方向更加智能的趋向于终点,所以其搜索深度较小,搜索的节点数少,故占用存储空间少,如图1所示。图1A*算法与Dijkstra算法搜索区域对比A*算法的估价函数A*算法的关键在于设计一个合适的启发函数。有文献对其特点进行了分析,认为启发函数f*(j)值是非递减的,只要能够满足相容性条件即估价函数h*(j)小于节点j到目标点的实际费用,它生成的路径一定是最优的。许多文献都在估价函数的构造中引入了距离和方向两个要素,即:h*(j)=w1*L+w2*如图2所示。其中L表示当前节点到终点的欧氏距离,表示起点到当前节点的线段与当前节点到终点的线段的夹角即SjE,有文献也用到了中间节点与关联节点的线段和关联节点与终点的线段夹角NjE。w1和w2分别是距离和角度的加权值,w1和w2的取值范围分别为055-0.65和0.35-0.45。但距离和角度的单位不统一的问题不能忽略,即使角度的单位为弧度、距离的单位为千米,它们之间也很有可能出现距离值远大于角度值(即L)的情况,特别是在大区域路径规划过程中,问题更明显。沈阳大学课程设计说明书NO.5而当L时,方向不再有约束力,而使得估价函数失去意义。A*算法的运行结构当构造合适的估价函数后就要考虑算法的运行,目前大多数方法是将全部数据读入到内存当中,然后搜索最短路径。从理论上讲,A*算法可以通过搜索更少的节点完成最短路径的搜索。但是算法运行时,必须要考虑两个问题:一是数据读取的速度。即使可以很快地将数据读入到内存中,我们也还要考虑第二个问题,即系统内存的大小。如果系统内存足够大,在算法运行过程中,也将会出现对同一节点进行重复的搜索,从而降低算法的运行效率。针对数据的读取问题,有学者提出了基于限制区域的A*算法,减小数据的加载量。但是由于A*算法本身就是一种有损算法,这种方法很有可能搜索不到最短路径,特别是在考虑道路属性信息和交通限制信息时。图2估价函数构造示意图改进的A*算法（1）A*算法估价函数的改进针对A*算法估价函数所出现的问题,我们将距离和角度进行归一化处理,即首先计算当前节点所有关联节点相应的距离和角度值,然后求它们的平均值即L，从而使得估价函数变为:h*(j)=w1*L+w2*(5)其中:L=L/L(6)=/(7)归一化处理以后,只考虑距离和角度对路径的贡献,而不必考虑距离和角度的数值大小。从而避免了距离和角度单位不统一的问题。虽然算法的运行要增加计算量,但是我们可以通过进一步减小算法的搜索空间,改善算法的运行结构来提高算法的搜索效率。沈阳大学课程设计说明书NO.6针对算法运行效率的问题,建立k-d树空间索引结构,动态加载路网数据,从而提高算法效率不失为一个好方法。k-d树索引结构是k(k1)的二叉检索树,主要用于索引多属性的数据或多维点数据,它可以通过坐标快速的访问区域中的路网数据。在算法执行过程中,并非开始就装载所有的路网数据,而是根据算法的需要,读取节点的相关信息,或删除节点信息,虽然会增加运算过程中的I/O运算,但是这样可以避免无效数据的大量装载,占用大量的内存空间。例如,首先判断当前节点是否在确定的范围内,如果不在则装载相应区域的数据,如果在确定的范围内,则读取数据的相关信息,并进行节点扩展。然后,在此基础上计算路段的启发值,搜索最短路径。（2）A*算法的实现在算法的实现过程中,要构造两个链表。分别存储待扩展的节点和已扩展的节点,分别称为Open表和Close表。算法步骤如下:①初始化设置。将起点信息加载到Open表中,Close表赋值为空。令g(j)=0。②搜索距离当前节点最近的节点,即求f*(j)的最小值,将节点j从Open表中删除并加载到Close表中。判断节点j是否为终点,如果是,终点转向步骤4;否则转向步骤3。③判断节点j的节点信息是否在确定的范围内,如果在范围内,则扩展节点j;否则加载节点j的节点信息并进行扩展。转向步骤2。④从节点j开始,利用回溯的方法输出起始节点到目标节点的最优路径,以及最短距离,算法终止。在算法的运行过程中,避免了对同一节点的重复访问,极大地缩小了搜索空间,从而缩短了算法的运行时间。对改进后的A*算法进行了实验,在估价函数归一化处理前后的最短路径搜索结果如图3(a),(b)所示。图3a改进前的搜索路径沈阳大学课程设计说明书NO.7图3b改进后的搜索路径（3）实验采用郑州市地图,节点2606个,路段4127条,在corei5,8GB内存的PC机上运行。与其他算法的实验结果进行了对比,结果见表1。表中:T表示临时标记节点个数,N表示永久标记节点的个数,D表示规划路径长度。表1算法比较图4临时标记节点个数比较沈阳大学课程设计说明书NO.8图5永久标记节点个数比较将表1数据中的临时标记节点,永久标记节点比较关系用图4、图5表示。通过实验由图4可以看出,归一化处理后的A*算法的搜索区域明显减小,由表1可以看出A*算法的搜索效率要比Dijkstra算法的搜索效率高。由图4、图5可知,改进后的A*算法的搜索效率明显要高,在利用k-d树建立空间索引结构以后,使得搜索的点数明显减少,特别是在区域比较大时,改进后的A*算法的效率提高得更加明显。需要指出的是,由于A*算法本身就是有损算法,所以其寻找到的路径长度一般要比Dijkstra算法的规划结果要长,但由于所选的道路更加合理,所以改进后算法的搜索结果更加实用。4．设计体会通过这次的课程设计，利用A*算法求解最短路径，加深了对