搜索
．引言图论是计算机科学中的一个重要研究工具，它产生于欧拉（Euler）对图的连通性的研究，但直到本世纪计算机诞生以后才得最迅猛的发展。图论中的最短路径问题在计算机中有着广泛的应用，例如网络通信中最短路由的选择，人工智能中搜索算法的研究等。本文对几种常见最短路径的算法进行介绍，尤其是在1968年发展起来的A*算法。二．常用算法简介为叙述的方便，本文中假定所有图均以邻接矩阵表示，并将图论中的常用符号列于下：G---------------------无向图或有向图A=[aij]----------------图G的邻接矩阵表示V(G)------------------图G的顶点数ε(G)-----------------图G的边数。1.Floyd算法这是几种最短路径算法中最简单的一种，本文不详细介绍，仅给出算法描述。算法：Fork:=1tondoFori:=1tondoForj:=1tondoIfA[i,j]+A[k,j]A[i,j]thenA[i,j]=a[i,k]+a[k,j];易知该算法的复杂度为o(n3)。执行该算法后矩阵A中aij即为点i与点j间的最短路径，若要求路径的具体行程，需在算法中以数组保存路径的改变信息，这里不再介绍。2.Dijkstra算法这种算法是Dijkstra于1959年提出的，主要用于计算图G中的某一点u0到其它点的最短距离。算法：Step1:令l(u0)=0;l(v)=∞;v≠u0S0={u0};v=0;Step2:vÎ┑Si=V(G)-Sil(v)=min{l(v),l(uI)+ω(ui,v)}设uI+1是使l(v)取到最小值的┑Si中的点。令Si+1=Si∪{ui+1}Step3:Ifi=γ(G)-1thenStop.Ifiγ(G)-1theni=i+1,GotoStep2.该算法的复杂度为o(n2)。它与Floyd算法相比，优点在于计算量小，缺点是每次只能计算出图G中的一个点到其它点的最短路径，但由于网络通信中对路由的选择只需计算当前点与它点的距离，故此法得以广泛应用。3.广度优先搜索算法(Broad-First-Search)广度优先搜索算法是一种搜索策略，与之相对应的还有深度优先搜索算法。广度优先是指从图G中的某点为始点出发，标记出所有与之相邻的点，并再以所有与之相邻的点为始点，搜索所有与这些点相邻的点，从而逐层向下扩展，实现对图的遍历。同理，深度优先搜索是指从某点出发，逐层向下扩展，直到无路可扩展时向上回溯，它是优先考虑图的深度（指从某点的扩展深度），而广度优先则优先考虑图的广度（指从某点的可扩展量）。由于该算法仅提供出一种搜索的策略，故它不仅可用于最短路径的搜索，事实上，图论中有很多问题均可通过此类搜索策略而得到实现。本文提出它只是因为在A*算法中，其部分地用到了该算法的思想。这里仅给出它的思想，不再对它在最短路径中的应用介绍。算法：Step1:vÎV(G),令l(v)=0,l=0Step2:If所有标号为l的顶点u的相关联的边皆已标号时，ThenGotoStep3。Else把与u相关联的边的未标号的顶点标以l+1，并记录这些边。令l=l+1，Goto(2)。Step3:Stop。4.动态规划算法这种算法利用动态规划理论求解最短路径，即将始点到终点的路程分为若干状态，从而将之转化为多阶段决策问题，这样就可用动态规划理论来解决。但这也必然决定了它的局限性，即只有求解可进行状态划分的问题，而事实上有很多问题是不能进行如是转化的，但这种算法却是在这种特殊条件下的最佳算法，因而也得到一些应用，这里不再详述。三．A*算法1.简介A*算法是到目前为止最快的一种计算最短路径的算法，但它一种‘较优’算法，即它一般只能找到较优解，而非最优解，但由于其高效性，使其在实时系统、人工智能等方面应用极其广泛。A*算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如Dijkstra算法）。它通过一个估价函数（HeuristicFunction）f(h)来估计图中的当前点p到终点的距离(带权值)，并由此决定它的搜索方向，当这条路径失败时，它会尝试其它路径。因而我们可以发现，A*算法成功与否的关键在于估价函数的正确选择，从理论上说，一个完全正确的估价函数是可以非常迅速地得到问题的正确解答，但一般完全正确的估价函数是得不到的，因而A*算法不能保证它每次都得到正确解答。一个不理想的估价函数可能会使它工作得很慢，甚至会给出错误的解答。为了提高解答的正确性，我们可以适当地降低估价函数的值，从而使之进行更多的搜索，但这是以降低它的速度为代价的，因而我们可以根据实际对解答的速度和正确性的要求而设计出不同的方案，使之更具弹性。2.实现限于A*算法实现上的复杂，这里不能给出具体的算法流程，下面分几个部分对A*算法实现中的几个关键性问题加以阐述。3.数据结构众所周知，对图的表示可以采用数组或链表，而且这些表示法也各也优缺点，数组可以方便地实现对其中某个元素的存取，但插入和删除操作却很困难，而链表则利于插入和删除，但对某个特定元素的定位却需借助于搜索。而A*算法则需要快速插入和删除所求得的最优值以及可以对当前结点以下结点的操作，因而数组或链表都显得太通用了，用来实现A*算法会使速度有所降低。要实现这些，可以通过二分树、跳转表等数据结构来实现，我采用的是简单而高效的带优先权的堆栈，经实验表明，一个1000个结点的图，插入而且移动一个排序的链表平均需500次比较和2次移动；未排序的链表平均需1000次比较和2次移动；而堆仅需10次比较和10次移动。需要指出的是，当结点数n大于10，000时，堆将不再是正确的选择，但这足已满足我们一般的要求。还有一种更好的方法是HotQueues，而且这种方法还可应用于Dijkstra算法以降低其复杂度。当我们移动估价函数值为f的结点时，我们插入值为f+δ(δ=C)(若δ=0将意味着估价函数是有效的，反之亦然)，常量C为从一个结点到相邻结点的权的最大改变。同时我们用一些“容器”来保存估价函数值的子集（这正如o(n)的排序算法的思想）,例如，当有10个“容器”时，堆将平均只包含1/10的估价值。因而这将比用堆更为有效。4.估价函数（HeuristicFunction）估价函数的正确选取将直接关系到A*算法的成功与否，而函数的确定却与实际情形有着密切的关系。在本文中，仅对网格状地图的估价函数作部分讨论，而在其它情形中，需要作不同的分析，但至少估价函数应为连续函数。a.ManhattanDistance这是一种标准的估价函数，h(A)=10*(abs(A.x-goal.x)+abs(A.y-goal.y))b.DiagonalDistance如果在地图上允许作斜线方向的运动，则MahattanDistance修正为DiagonalDistanceh(A)=max(abs(A.x-goal.x),abs(A.y-goal.y))5.估价函数的判优一般情形下，我们只需对估价函数的值进行比较而取其大者即可，但在几个结点的估价函数值相同的情形下，我们需要采取一定的策略来决定这几者谁更优，从而避免对多个点的搜索。从而如下代码可实现之：doubledx1=currentX-goalX;doubledy1=currentY-goalY;doubledx2=startX-goalX;doubledy2=startY-goalY;cross=dx1*dy2-dx2*dy1;if(cross0)cross=-cross;...addcross*0.001totheheuristic...这段代码计算始点、当前点和终点的矢量积，从而可以判断这三点是否共线（或近似共线），这样不同点间即使有微小的差别也会被放大，从而更利于判断。6.改进的A*算法a.BeamSearch在A*算法中需要保留所有的结点，这将使得时间和空间的消耗都很大，而BeamSearch方法对结点数作出限期，当结点数过多时，它会将一些不(大)可能为最优的点排除，从而降低时间和空间的要求，但需要说明的是，由于在排除结点后需对结点排序，当排序的工作量大于排除点后所节省的工作量，则该方法无意义。b.Iterativedeepening这是一种在人工智能中常使用的方法，它首先产生一近似值，然后对它进行修正而逐步接近最优解。这其实在一种博奕算法的变形。c.Dynamicweighting这种算法是基于这样的考虑，即在搜索初期以速度优先，在搜索后期以准确度优先(这可通过对搜索初、后期赋予不同的权值来实现)。即：f(p)=g(p)+w(p)*h(p)d.Bidirectionalsearch这种算法从起点和终点同时应用A*算法，直到有结点相遇。其缺点在于复杂度太大，一般仅用于复杂的图形。e.HierarchicalA*这种算法思想是将搜索过程化，对每个简单过程求解从而得全局较优解。正如当我们到另一城市时，可分解为从家里“搜索”一条路径至车站，再从车站“搜索”一条路径到另一城市，当我们从家里出发时，需要考虑的是怎样尽快地到达车站，而不是怎样尽快地到另一城市。f.DynamicA*(D*)这种算法主要用于人工智能和机器人技术。由于A*算法一开始要求获得全部信息，而这在实际中有时是不可能的，而D*算法就是在假定信息不完整的前提下应用A*算法，但它会随着得到信息的增多而不断改进结果，这就决定了它对空间的要求相当高，因为它需要保留以前的所有获得信息及运算情形。四．结论A*算法作为解决最优路径的一种高效算法，自从1968年诞生以来，得到了广泛的应用，而其的多种改进算法也在许多领域发挥着作用。可以预见，在更优的算法发现以前，A*算法将会得到更广泛的应用，并会由于图论、人工智能、机器人技术、自动控制等多学科的融合而得到更大的发展。参考文献：[1]卢开澄、卢华明，图论及其应用（第二版），北京，清华大学出版社，1982[2]ComputerNetworks(ThirdEdition)，AndrewS.Tanenbaum，PrenticeHallInternational,Inc.,1998[3]Russell&Norvig，AI:AModernApproach[4]Ginsberg，EssentialsofArtificialIntelligence