最短路径算法

算法的思想 算法的描述 算法的举例 TOC\o"1-5"\h\zA*算法 2原理简介 2详细内容 2A*算法误区 17\o"CurrentDocument"A*算法总结SummaryoftheA*Method) 17\o"CurrentDocument"Floyd算法 17\o"CurrentDocument"定义 17\o"CurrentDocument"核心思路 18\o"CurrentDocument"算法过程 18\o"CurrentDocument"优缺点分析 18\o"CurrentDocument"Johnson算法 23\o"CurrentDocument"Johnson算法要求 23Johnson算法结构要求 23Johnson算法数据结构. 23\o"CurrentDocument"Johnson算法的内容 23\o"CurrentDocument"Johnson算法源程序 23\o"CurrentDocument"DIJKSTRA算法 27\o"CurrentDocument"算法简介 27\o"CurrentDocument"算法描述 27\o"CurrentDocument"复杂度分析 27\o"CurrentDocument"算法实现 28测试样例 30\o"CurrentDocument"算法应用的实例 34算法的思想设图中有n个结点，设置一个集会u,存放已经求出最短路径的结点(初始时u中的元素是源点)，v-u是尚未确定最短路径的顶点的集合。每次从v-u集合中找这样一个结点best_j：best_j是u集合中结点的邻接点，到源点的距离最短(等于到父结点的距离加上父结点到源点的距离)。然后把该best_j置入u集合中，直到u=v。算法的描述最短路经计算分静态最短路计算和动态最短路计算。静态路径最短路径算法是外界环境不变，计算最短路径。主要有Dijkstra算法，A*算法。动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。典型的有D*算法。算法的举例A*算法原理简介A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n),其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件，关键在于估价函数h(n)的选取：估价值h(n)＜=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值＞实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。例如对于几何路网来说，可以取两节点间欧几理德距离(直线距离)做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。conditionsofheuristicOptimistic(mustbelessthanorequaltotherealcost)Asclosetotherealcostaspossible详细内容初始A*算法主要搜索过程：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,-＞算X的估价值->While(OPEN!=NULL){从OPEN表中取估价值f最小的节点n;if(n节点==目标节点)break;else{if(XinOPEN)比较两个X的估价值f//注意是同一个节点的两个不同路径的估价值if(X的估价值小于OPEN表的估价值)更新OPEN表中的估价值;〃取最小路径的估价值if(XinCLOSE)比较两个X的估价值//注意是同一个节点的两个不同路径的估价值if(X的估价值小于CLOSE表的估价值)更新CLOSE表中的估价值；把X节点放入OPEN//取最小路径的估价值if(Xnotinboth)求X的估价值；并将X插入OPEN表中;〃还没有排序}将n节点插入CLOSE表中；按照估价值将OPEN表中的节点排序；〃实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点(除非该节点是死节点)，在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f(n)=g'(n)+h'(n)这里，f(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可(大多数情况下都是满足的，可以不用考虑)，h(n)代替h'(n)，但h(n)<=h'(n)才可(这一点特别的重要)。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。当然它是一种最臭的A*算法。再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。概述虽然掌握了A*算法的人认为它容易，但是对于初学者来说，A*算法还是很复杂的。搜索区域(TheSearchArea)我们假设某人要从A点移动到B点，但是这两点之间被一堵墙隔开。如图1，绿色是A，红色是B，中间蓝色是墙。图1你应该注意到了，我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域，就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了2维数组。数组的每一项代表一个格子，它的状态就是可走(walkalbe)和不可走(unwalkable)。通过计算出从A到B需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。方格的中心点我们成为“节点(nodes)”。如果你读过其他关于A*寻路算法的文章，你会发现人们常常都在讨论节点。为什么不直接描述为方格呢？因为我们有可能把搜索区域划为为其他多变形而不是正方形，例如可以是六边形，矩形，甚至可以是任意多变形。而节点可以放在任意多边形里面，可以放在多变形的中心，也可以放在多边形的边上。我们使用这个系统，因为它最简单。开始搜索(StartingtheSearch)一旦我们把搜寻区域简化为一组可以量化的节点后，就像上面做的一样，我们下一步要做的便是查找最短路径。在A*中，我们从起点开始，检查其相邻的方格，然后向四周扩展，直至找到目标。我们这样开始我们的寻路旅途：从起点A开始，并把它就加入到一个由方格组成的openlist(开放列表)中。这个openlist有点像是一个购物单。当然现在openlist里只有一项，它就是起点A，后面会慢慢加入更多的项。Openlist里的格子是路径可能会是沿途经过的，也有可能不经过。基本上openlist是一个待检查的方格列表。查看与起点A相邻的方格(忽略其中墙壁所占领的方格，河流所占领的方格及其他

非法地形占领的方格)，把其中可走的(walkable)或可到达的(reachable)方格也加入到openlist中。把起点A设置为这些方格的父亲(parentnode或parentsquare)。当我们在追踪路径时，这些父节点的内容是很重要的。稍后解释。3.把A从openlist中移除，加入到closelist(封闭列表)中，closelist中的每个方格都是现在不需要再关注的。如下图所示，深绿色的方格为起点，它的外框是亮蓝色，表示该方格被加入到了closelist。与它相邻的黑色方格是需要被检查的，他们的外框是亮要从§1计算出组成路径的方格的关键是下面这个等式:绿色。每个黑方格都有一个灰色的指针指向他们的父节点，这里是起点A。要从§1计算出组成路径的方格的关键是下面这个等式::点A相邻的方格，按下面描述的一样或各好呢？具有最小F值的那个。F=G+H这里，G=从起点A移动到指定方格的移动代价，沿着到达该方格而生成的路径。H=从指定的方格移动到终点B的估算成本。这个通常被称为试探法，有点让人混淆。为什么这么叫呢，因为这是个猜测。直到我们找到了路径我们才会知道真正的距离，因为途中有各种各样的东西(比如墙壁，水等)。我们的路径是这么产生的：反复遍历openlist，选择F值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。如上所述，G是从起点A移动到指定方格的移动代价。在本例中，横向和纵向的移动代价为10，对角线的移动代价为14。之所以使用这些数据，是因为实际的对角移动距离是2的平方根，或者是近似的1.414倍的横向或纵向移动代价。使是有10和14就是为了简单起见。比例是对的，我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现，如果不使用这些技巧，寻路算法将很慢。既然我们是沿着到达指定方格的路径来计算G值，那么计算出该方格的G值的方法就是找出其父亲的G值，然后按父亲是直线方向还是斜线方向加上10或14。随着我们离开起点而得到更多的方格，这个方法会变得更加明朗。有很多方法可以估算H值。这里我们使用Manhattan方法，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以 10。之所以叫做Manhattan方法，是因为这很像统计从一个地点到另一个地点所穿过的街区数，而你不能斜向穿过街区。重要的是，计算H是，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此才称为试探法。把G和H相加便得到F。我们第一步的结果如下图所示。每个方格都标上了F，G，H的值，就像起点右边的方格那样，左上角是F，左下角是G，右下角是H。

因为水平方向方格的G值都是10，对角线的方格G值都是14。H值通过估算起点于终点（红色方格）的Manhattan距离得到，仅作横向和纵向移动，并且忽略沿途的墙壁。使用这种方式，起点右边的方格到终点有3个方格的距离，因此H=30。这个方格上方的方格到终点有4个方格的距离（注意只计算横向和纵向距离），因此H=40。对于其他的方格，可以用同样的方法知道H值是如何得来的。每个方格的F值，再说一次，直接把G值和H值相加就可以了。继续搜索（ContinuingtheSearch）为了继续搜索，我们从openlist中选择F值最小的（方格）节点，然后对所选择的方格作如下操作：把它从openlist里取出，放到closelist中。检查所有与它相邻的方格，忽略其中在closelist中或是不可走（unwalkable）的方格（比如墙，水，或是其他非法地形），如果方格不在openlsit中，则把它们加入到openlist中。把我们选定的方格设置为这些新加入的方格的父亲。,起点被放入如果某个相邻的方格已经在openlist中，则检查这条路径是否更优，也就是说经由当前方格（我们选中的方格）到达那个方格是否具有更小的G值。如果没有，不做任何操作。相反，如果G值更小，则把那个方格的父亲设为当前方格（我们选中的方格），然后重新计算那个方格的F值和G值。如果你还是很混淆，请参考下图。

,起点被放入了closelist中。在这些方格中，起点右边的格子的F值40最小，因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。首先，我们把它从openlist移到closelist中（这就是为什么用蓝线打亮的原因了）。然后我们检查与它相邻的方格。它右边的方格是墙壁，我们忽略。它左边的方格是起点，在closelist中，我们也忽略。其他4个相邻的方格均在openlist中，我们需要检查经由这个方格到达那里的路径是否更好，使用G值来判定。让我们看看上面的方格。它现在的G值为14。如果我们经由当前方格到达那里，G值将会为20（其中10为到达当前方格的G值，此外还要加上从当前方格纵向移动到上面方格的G值10）。显然20比14大，因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。当把4个已经在openlist中的相邻方格都检查后，没有发现经由当前方格的更好路径，因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格，并也对他们作了处理，是时候选择下一个待处理的方格了。因此再次遍历我们的openlist，现在它只有7个方格了，我们需要选择F值最小的那个。有趣的是，这次有两个方格的F值都54，选哪个呢？没什么关系。从速度上考虑，选择最后加入openlist的方格更快。这导致了在寻路过程中，当靠近目标时，优先使用新找到的方格的偏好。但是这并不重要。（对相同数据的不同对待，导致两中版本的A*找到等长的不同路径）。我们选择起点右下方的方格，如下图所示。们把

动到I,隼。我方格移意：穿越墙角的规则是可选的，依赖于你的节点是怎么放置的）这样还剩下5们把

动到I,前方格下面的2个方格还没有加入openlist，所以把它们加入，同时把当前方格设为他们的父亲。在剩下的3个方格中，有2个已经在closelist中（一个是起点，一个是当前方格上面的方格，外框被加亮的），我们忽略它们。最后一个方格，也就是当前方格左边的方格，我们检查经由当前方格到达那里是否具有更小的G值。没有。因此我们准备从openlist中选择下一个待处理的方格。不断重复这个过程，直到把终点也加入到了openlist中，此时如下图所示。

它右上方的方格。现在它的G值为20，并且指向它正上方的方格。这在寻路过程中的某处发生，使用新路径时G值经过检查并且变得更低，因此父节点被重新设置，G和F值被重新计算。尽管这一变化在本例中并不重要，但是在很多场合中，这种变化会导致寻路结果的巨大变化。那么我们怎么样去确定实际路径呢？很简单，从终点开始，按着箭头向父节点移动，这样你就被带回到了起点，这就是你的路径。如下图所示。从起点A移动到终点B就是简单从路径上的一个方格的中心移动到另一个方格的中心，直至目标图7。就是这么简单图7图7代码如下：namespaceAStar{classPoint

{publicPoint(){}publicPoint(intx,inty){this.x=x;this.y=y;}privateintx;publicintX{get{returnx;}set{x=value;}}privateinty;publicintY{get{returny;}set{y=value;}} }classPath{privateinth;publicintH{get{returnh;}set{h=value;} }privateintf;publicintF{get{returnf;}set{f=value;}}privateintg;publicintG{get{returng;}set{g=value;}}privatePointstartPoint;publicPointStartPoint{get{returnstartPoint;}set{startPoint=value;}}privatePointendPoint;publicPointEndPoint{get{returnendPoint;}set{endPoint=value;}} } }namespaceAStar{classProgram{privatestaticArrayListcloselist=newArrayList();privatestaticArrayListopenlist=newArrayList();privateprivatestaticPointp_start=newPoint(0,0);privateprivatestaticPointp_end=newPoint(9,9);privatestaticintgw=10,privatestaticintgw=10,gwh=14;///gh=10,privatestaticintw=10,h=10;//privatestaticstringn_path=privatestaticprivatestaticintw=10,h=10;//privatestaticstringn_path=privatestaticPaths_path=newPath();privatestaticintnum;staticvoidMain(string[]args){inth=(Math.Abs(p_end.X-p_start.Y)+Math.Abs(p_end.Y-p_start.Y))*gw;s_path.F=h;s_path.G=0;s_path.H=h;s_path.StartPoint=p_start;s_path.EndPoint=p_start;do{GetF(setDirection(s_path.StartPoint));Sort(openlist);s_path=(Path)openlist[openlist.Count-1];closelist.Add(s_path);openlist.RemoveAt(openlist.Count-1);if(openlist.Count==0){Console.WriteLine("找不到路径");return;}if((s_path.StartPoint.X==p_end.X)&&(s_path.StartPoint.Y==p_end.Y)){getPath();break;}}while(true);}staticArrayListsetDirection(PointstartPoint){ArrayListdirection=newArrayList();PointnorthEast=newPoint();northEast.X=startPoint.X+1;northEast.Y=startPoint.Y-1;direction.Add(northEast);//东北Pointeast=newPoint();east.X=startPoint.X+1;east.Y=startPoint.Y;direction.Add(east);//东PointsouthEast=newPoint();southEast.X=startPoint.X+1;southEast.Y=startPoint.Y+1;direction.Add(southEast);//东南Pointsouth=newPoint();south.X=startPoint.X;south.Y=startPoint.Y+1;direction.Add(south);//南PointsouthWest=newPoint();southWest.X=startPoint.X-1;southWest.Y=startPoint.Y+1;direction.Add(southWest);//西南Pointwest=newPoint();west.X=startPoint.X-1;west.Y=startPoint.Y;direction.Add(west);//西PointnorthWast=newPoint();northWast.X=startPoint.X-1;northWast.Y=startPoint.Y-1;direction.Add(northWast);//西北Pointnorth=newPoint();north.X=startPoint.X;north.Y=startPoint.Y-1;direction.Add(north);//西北returndirection;}staticvoidGetF(ArrayListarr){int[]t=newint[2];intG,H,F;for(inti=0;i<arr.Count;i++){t[0]=((Point)arr[i]).X;t[1]=((Point)arr[i]).Y;if(IsOutScreen((Point)arr[i])||IsPass((Point)arr[i])||IsClose((Point)arr[i])||IsStart((Point)arr[i])||!IsInTurn((Point)arr[i]))continue;if((t[0]-s_path.StartPoint.X)*(t[1]-s_path.StartPoint.Y)!=0)G=s_path.G+gwh;elseG=s_path.G+gw;if(InOpen((Point)arr[i])){if(G<((Path)openlist[num]).G){((Path)openlist[num]).F=(G+((Path)openlist[num]).H);((Path)openlist[num]).G=G;((Path)openlist[num]).EndPoint=s_path.StartPoint;}else{G=((Path)openlist[num]).G;} }else{H=(Math.Abs(p_end.X-t[0])+Math.Abs(p_end.Y-t[1]))*gw;F=G+H;Pathp=newPath();p.F=F;p.G=G;p.H=H;p.StartPoint=(Point)arr[i];p.EndPoint=s_path.StartPoint;openlist.Add(p);}} }staticboolIsStart(Pointarr){if(arr.X==p_start.X&&arr.Y==p_start.Y)returntrue;returnfalse;}staticboolIsInTurn(Pointarr){if(arr.X>p_start.X){if(arr.Y>p_start.Y)if(IsPass(newPoint(arr.X-1,arr.Y))||IsPass(newPoint(arr.X,arr.Y-1)))returnfalse;}elseif(arr.Y<p_start.Y){if(IsPass(newPoint(arr.X-1,arr.Y))||IsPass(newPoint(arr.X,arr.Y+1)))returnfalse;} }elseif(arr.X<p_start.X){if(arr.Y>p_start.Y){if(IsPass(newPoint(arr.X+1,arr.Y))||IsPass(newPoint(arr.X,arr.Y-1)))returnfalse;}elseif(arr.Y<p_start.Y){if(IsPass(newPoint(arr.X+1,arr.Y))||IsPass(newPoint(arr.X,arr.Y+1)))returnfalse;} }returntrue;}staticboolIsOutScreen(Pointarr){if(arr.X<0||arr.Y<0||arr.X>(w-1)||arr.Y>(h-1))returntrue;returnfalse;}staticboolInOpen(Pointarr){boolresult=false;for(inti=0;i<openlist.Count;i++){if(arr.X==((Path)openlist[i]).StartPoint.X&&arr.Y==((Path)openlist[i]).StartPoint.Y){result=true;num=i;break;}}returnresult;}staticboolIsClose(Pointarr){boolresult=false;for(inti=0;i<closelist.Count;i++){if((arr.X==((Path)closelist[i]).StartPoint.X)&&(arr.Y==((Path)closelist[i]).StartPoint.Y)){result=true;break;}}returnresult;}staticboolIsPass(Pointpos){if(Map[pos.X,pos.Y]>1)returntrue;returnfalse;}staticvoidSort(ArrayListarr){Pathtemp;for(inti=0;i<arr.Count;i++){if(arr.Count==1)break;if(((Path)arr[i]).F<=((Path)arr[i+1]).F){temp=(Path)arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}if((i+1)==(arr.Count-1))break;}}staticvoidgetPath(){stringstr="”;Pointt=((Path)closelist[closelist.Count-1]).EndPoint;while(true){str+="("+t.X+","+t.Y+")”;for(inti=0;i<closelist.Count;i++){if(((Path)closelist[i]).StartPoint.X==t.X&&((Path)closelist[i]).StartPoint.Y==t.Y)t=((Path)closelist[i]).EndPoint;}if(t.X==p_start.X&&t.Y==p_start.Y)break;}Console.WriteLine(str);}staticint[,]Map={TOC\o"1-5"\h\z{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },{ 1, 1, 1, 1, 1, 2, 1, 1, 1, 1 },{ 1, 1, 1, 1, 2, 3, 2, 1, 1, 1 },{ 1, 1, 1, 2, 3, 4, 3, 2, 1, 1 },{ 1, 1, 2, 3, 4, 5, 4, 3, 2, 1 },{ 1, 1, 1, 2, 3, 4, 3, 2, 1, 1 },{ 1, 1, 1, 1, 2, 3, 2, 1, 1, 1 },{ 1, 1, 1, 1, 1, 2, 1, 1, 1, 1 },{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }深入A*算法如图有如下的状态空间：（起始位置是人，目标位置是P,字母后的数字表示节点的估价值）搜索过程中设置两个表：Open和closed。open表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。具体搜索过程如下：1） 初始状态：OPEN=[A5]；CLOSED=[]；2） 估算A5，取得搜有子节点，并放入OPEN表中；OPEN=[B4，C4，D6]；CLOSED=[A5]3） 估算B4，取得搜有子节点，并放入OPEN表中；OPEN=[C4,E5，F5，D6]；CLOSED=[B4，A5]4） 估算C4；取得搜有子节点，并放入OPEN表中；OPEN=[H3,G4,E5,F5,D6]；CLOSED=[C4,B4,A5]估算H3,取得搜有子节点，并放入OPEN表中；OPEN=[O2,P3,G4,E5,F5,D6]；CLOSED=[H3,C4,B4,A5]估算O2，取得搜有子节点，并放入OPEN表中；OPEN=[P3，G4,E5,F5,D6]；CLOSED=[O2,H3,C4,B4,A5]估算P3，已得到解；看了具体的过程，再看看伪程序吧。算法的伪程序如下：Best_First_Search(){Open=[起始节点];Closed=[];while(Open表非空){从Open中取得一个节点X，并从OPEN表中删除。if(X是目标节点){求得路径PATH返回路径PATH}for(每一个X的子节点Y){if(Y不在OPEN表和CLOSE表中){求Y的估价值；并将Y插入OPEN表中；}elseif(Y在OPEN表中){if(Y的估价值小于OPEN表的估价值)更新OPEN表中的估价值；}else{if(Y的估价值小于CLOSE表的估价值){更新CLOSE表中的估价值；从CLOSE表中移出节点，并放入OPEN表中；} }将X节点插入CLOSE表中；按照估价值将OPEN表中的节点排序；} } }伪程序出来了，写一个源程序应该不是问题了，依葫芦画瓢就可以。A*算法的程序与此是一样的，只要注意估价函数中的g(n)的h(n)约束条件就可以了。不清楚的可以看看《初识A*算法》。我们可以进入另一个重要的话题，用A*算法实现最短路径的搜索。用A*算法实现最短路径的搜索A*算法的核心是估价函数f(n)，它包括g(n)和h(n)两部分。g(n)是已经走过的代价，h(n)是n到目标的估计代价。在这个例子中g(n)表示在状态空间从起始节点到n节点的深度，h(n)表示n节点所在地图的位置到目标位置的直线距离。啊！一个是状态空间，一个是实际的地图，不要搞错了。再详细点说，有一个物体A，在地图上的坐标是(xa,ya)，A所要到达的目标b的坐标是(xb,yb)。则开始搜索时，设置一个起始节点1，生成八个子节点2-9因为有八个方向。如图：仔细看看节点1、9、17的g(n)和h(n)是怎么计算。就知道下面程序中的f(n)是如何计算。其实这个程序是一个很典型程序，上面的伪程序，这个程序是十分容易理解的。不过他和上面的伪程序有一些的不同，我在后面会提出来。搜索主函数：voidAstarPathfinder::FindPath(intsx,intsy,intdx,intdy)(NODE*Node,*BestNode;intTileNumDest;TileNumDest=TileNum(sx,sy);OPEN=(NODE*)calloc(1,sizeof(NODE));CLOSED=(NODE*)calloc(1,sizeof(NODE));Node=(NODE*)calloc(1,sizeof(NODE));Node->g=0;Node->h=(dx-sx)*(dx-sx)+(dy-sy)*(dy-sy);Node->f=Node->g+Node->h;Node->NodeNum=TileNum(dx,dy);Node->x=dx;Node->y=dy;OPEN->NextNode=Node;for(;;)(BestNode=ReturnBestNode();if(BestNode->NodeNum==TileNumDest)GenerateSuccessors(BestNode,sx,sy);}PATH=BestNode;}生成子节点函数：voidAstarPathfinder::GenerateSuccessors(NODE*BestNode,intdx,intdy)(intx,y;if(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);if(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);}最重要的函数：voidAstarPathfinder::GenerateSucc(NODE*BestNode,intx,inty,intdx,intdy){intg,TileNumS,c=0;NODE*Old,^Successor;g=BestNode->g+1;TileNumS=TileNum(x,y);if((Old=CheckOPEN(TileNumS))!=NULL){for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)break;BestNode->Child[c]=Old;if(g<Old->g){Old->Parent=BestNode;Old->g=g;Old->f=g+Old->h;}}elseif((Old=CheckCLOSED(TileNumS))!=NULL){for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)break;BestNode->Child[c]=Old;if(g<Old->g){Old->Parent=BestNode;Old->g=g;Old->f=g+Old->h;PropagateDown(Old);}}Else{Successor=(NODE*)calloc(1,sizeof(NODE));Successor->Parent=BestNode;Successor->g=g;Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);Successor->f=g+Successor->h;Successor->x=x;Successor->y=y;Successor->NodeNum=TileNumS;Insert(Successor);for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)break;BestNode->Child[c]=Successor;}}A*算法误区A*是一个启发式搜索算法。就是说在一个可以被穷举的有限解空间集中，用比较有效的方法(主要是利用估价函数)求出最优解的算法°A*跟寻路算法没有太多关系，我们只是借助了这个方法来解决寻路这个问题，正如四则运算对于数学题一样，它只是一个基本工具。寻路算法本身有很多种，我们找到算法后，借助A*这个工具实现这个算法而已。A*算法理论上可以得到最优解，不过我们可以通过选择一个更好的估价函数，或是减少解空间来提高性能。A*是传统意义上的地图寻路，其实依据的是这样一种算法：把地图分成若干个格子，反复迭代下去把地图分格子，给格子间的路径一个权值(前面的例子中，格子间的距离都是相等的，我们也可以根据地形划分成不等的距离，即权值，或者定义单向道路，这都是可以的)，这是解决寻路问题的关键，但都不是A*算法的范畴。这种一步步尝试的过程，就是一种搜索过程。如果加上启发函数，不让它盲目的寻找，就衍生出很多启发式搜索算法。A*是其中的一种。之所以加一个*号，是因为它的启发式函数是有限制的，这个限制确保它能找到绝对最优解，去掉这个限制，就是A算法了。如果你想出某种算法，比如把地图划分成不规则的区域，或者把地图矢量化。依然可以再此基础上用A*算法这个工具来从中求到最优解。如果想别的方法来寻路，比如拟人的判断，预设路点等等，甚至按走迷宫的方法一样，分叉右转，碰壁回头，那些可以算是对分格寻路方法的一些改进，却都不关A*什么事情。A*算法总结(SummaryoftheA*Method)把起点加入openlist。重复如下过程：遍历openlist，查找F值最小的节点，把它作为当前要处理的节点。把这个节点移到closelist。对当前方格的8个相邻方格的每一个方格？♦如果它是不可抵达的或者它在closelist中，忽略它。否则，做如下操作。♦如果它不在openlist中，把它加入openlist，并且把当前方格设置为它的父亲，记录该方格的F，G和H值。♦如果它已经在openlist中，检查这条路径(即经由当前方格到达它那里)是否更好，用G值作参考。更小的G值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的G和F值。如果你的openlist是按F值排序的话，改变后你可能需要重新排序。停止，当你♦把终点加入到了openlist中，此时路径已经找到了，或者♦查找终点失败，并且openlist是空的，此时没有路径。保存路径。从终点开始，每个方格沿着父节点移荻直至起点，这就是你的路径。Floyd算法定义Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]nxn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为0*3);其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表示i到j的最短距离K是穷举i,的断点map[n,n]初值应该为0，或者按照题目意思来做。当然，如果这条路没有通的话，还必须特殊处理 ，比如没有map[i,k]这条路算法过程把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离， G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，贝0D[i,j]=k。在G中包含有两点之间最短道路的信息， 而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。优缺点分析Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。如何用floyd算法求出最短路径一：flody是如何实现搜索最短路径的：

Floyd又称插点法，它的基本过程如下：首先用图邻接矩阵G表示出来，如果从Vi到Vj有路可达。则G(I,j)=d,d表示该路长度，否则G(I,j)=inf,最后图可以用如下图表示：G=02hfhfi)104[nf4Inf1]0Inf10In：10rr.r90InfInf7Inf210041S4Inf0为了搜索出最短路径我们还需要一个矩阵用来记录所插入点的信息，这个矩阵的D，D(i,j)表示从V(i)到V(j)需要经过的点，初始化D(I,j)=jD=然后把各个顶点插入图中，比较插点后的距离与原来的距离，G(I,j)=min(G(I,j)+G(I,k)+G(k,j)),如果G(I,j)的值变小，则G(I,j)=k,如在上个图中把Vi的值插入后所得结果为G=(J23Inf[if9I0•1]nf011)110]nfl(i101090Int07E2to0414Inf0D=

124612345：■123451134511□345f]111456这样我们把各个值都加入后得到G为G=02.1It)2fiI02X04110g1?10】0勺0101433280413■1430D=1262512：&512362IJ43536h111426二：如何搜索出最短路径：在G中包含有最短道路的消息，而在D中则包含有最短通路径的信息，如果我从V5到V1的路径则根据D,D(5,1)=3则说名点经过V3，道路为(V5,V3,V1),D(5,3)=3,说明V5与V3直接连接，D(3,1)=1，说明V3与V1直接相连，具体算法是建立一个表，Vi为头，以Vj为尾，如果D(i.j)习则完结，否则Vh=Vi,Vk0=Vj转(2)如果k(m)=D(h,k(m)),装(4)，否则转(3)k(m+1)=D(h,k(m))把Vk(m+1)插在Vh,Vk(m)之间，返(2)如果k(m)=j,则完结，否则Vh=Vk(m),Vk(m)=Vk(m-1);

如上图经过图中搜索可得到一条较长的道路是从V8如上图经过图中搜索可得到一条较长的道路是从V8到V200,依次经过的顶点为182{8,21,22,27,28,29,51,62,83,90,100,110，126,136,151，150,164，177,178，179,180,181，185，195,197,200}182弗洛伊德Floyd算法思想：递推地产生一个矩阵序列dist(0)dist⑴...dist(n)其中dist(0)=costcost为邻接矩阵元素dist(0)[i,j]表示从顶点Vi到顶点Vj，中间经过的顶点序号M0(即不经任何其他顶点)的最短路径长度。最后dist(n)[i,j]表示从vi到vj中间经过的顶点序号不大于n的最短路径长度。即为所求。dist(k)[i,j]是从vi到vj的中间经过顶点序号Mk的最短路——k型最短路。VIV2V3V4VI-oV215p6侦©yoooo4V4CC：'8 2001010615820dist(0)(i,j)=cost(i,j)dist(k)(i,j)=min{dist(k-l)(i,j),dist(k-l)(i,k)+dist(k-1)(k,j)}voidFloyd(GraphG,cost,path){for(i=1;i<=n;i++)//dist,path初始化for(j=1;j<=n;j++){dist[i][j]=cost[i][j];if(dist[i][j]<32767)path[i][j]={Vi}+{Vj};}for(k=1;k<=n;k++)〃递推产生dist序列for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(dist[i][k]+dist[k][j]{dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[i][k]+path[k][j];}}注意：Floyd算法中一种标准错误写法：请注意floyed算法的本质是动态规划！定义f(i,j,k)表示只用第0〜i个点从j走到k所用的最短路程。f(i,j,k)=min(f(i-1,j,k),f(i-1,j,i)+f(i-1,i,k))所以应该是for(inti=0;i<sz;i++)for(intj=0;j<sz;j++)for(intk=0;k<sz;k++){intt_dis=distances[j][i]+distances[i][k];if(distances[j][k]>t_dis)distances[j][k]=t_dis;}很多人没有弄懂floyed的本质就开始背“三个for”的代码，所以会出现这种标准错误答案。Johnson算法Johnson算法要求Johnson算法本身需要调用BELLMAN_FORD算法和SUKSTRA算法，所以需要另外实现这两个算法。Johnson算法结构要求不要全部放在一个函数中，分别为每个算法写个函数，然后通过函数调用实现，可以用类实现，把图的信息作为类的成员变量，每个函数作为类的成员函数；也可以不用类，就单独写几个函数，然后通过main函数直接调用。Johnson算法数据结构下面给的测试数据是用邻接矩阵存储的，大家实现算法的时候用什么方式存储都可以，如果用邻接表，把自己的数据转换成你需要的格式。但是输出的时候必须按照下面的要求，这样检查程序的时候也比较方便。Johnson算法的内容Johnson算法适用于求AllPairsShortestPath.Johnson算法应用了重标号技术，先进行一次Bellman-Ford算法，然后对原图进行重标号，w'(i,j)=h[i]-h[j]+w(i,j)。然后对每个点进行一次Dijkstra，每次Dijkstra的复杂度为O(nlogn+m)，于是算法复杂度为O(nA2logn+m)oJohnson算法源程序II、#include#include#definelensizeof(structnode)typedefstructnode(floatbound;intstaus[50];structnode*next;}node;intitem[50],wl,n,state[50];floatvalue[50],weight[50],max_value,ratio[50];voiddele(node*father,node*current){if(current->next==NULL){father->next=NULL;return;}father->next=current->next;}voidinit(node*father,node*son){inti;father->next=son;for(i=0;ison->staus[i]=0;son->next=NULL;}voidbranch(){inti,t,j;floatdiff,sum=0,sum_value=0;node*head,*sonbrother,*father,*son,*prenode,*p,*q;head=prenode=(node*)malloc(len);father=(node*)malloc(len);init(prenode,father);father->bound=32768;while(head->next!=NULL){son=(node*)malloc(len);init(father,son);for(i=0;istaus[i]!=0;i++)son->staus[i]=father->staus[i];t=i;son->staus[t]=-(t+1);sum=0;sum_value=0;for(j=0;jstaus[j]!=0;j++)if(son->staus[j]>0){sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}while(sum!=wl&&son->staus[n-1]==0){diff=wl-(sum+weight[item[j]]);if(diff>=0)(sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}else{sum=wl;sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];}j++;}son->bound=sum_value;sonbrother=(node*)malloc(len);init(son,sonbrother);for(i=0;isonbrother->staus[i]=father->staus[i];sonbrother->staus[t]=t+1;sum=0;sum_value=0;for(j=0;jstaus[j]!=0;j++)if(sonbrother->staus[j]>0){sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}if(sum>wl){sonbrother->bound=-32768;dele(son,sonbrother);}else{while(sum!=wl&&sonbrother->staus[n-1]==0){diff=wl-(sum+weight[item[j]]);if(diff>=0){sum=sum+weight[item[j]];sum_value=sum_value+value[item[j]];}else{sum=wl;sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];}j++;}sonbrother->bound=sum_value;}dele(prenode,father);father=prenode->next;if(son->staus[n-1]!=0){if(son->next!=NULL){max_value=sonbrother->bound;for(i=0;istate[i]=sonbrother->staus[i];dele(son,sonbrother);dele(prenode,father);father=prenode->next;}else{max_value=son->bound;for(i=0;istate[i]=son->staus[i];dele(prenode,father);}q=head;p=head->next;while((p!=NULL)&&(p->bound<=max_value)){dele(q,p);p=q->next;}if(p!=NULL){prenode=q;father=p;}elsereturn;}elseif(father->next!=NULL){prenode=prenode->next;father=father->next;} }return;}intgetmin(){inti;floatamin=weight[0];for(i=1;iif(amin>weight[i])amin=weight[i];returnamin;}voidsort(){inti,j,exchange=1;floattemp1,temp2;for(i=0;iratio[i]=value[i]/weight[i];for(j=n-1;j>=0&&exchange==1;j--){exchange=0;for(i=0;iif(ratio[i+1]>ratio[i]){exchange=1;temp1=ratio[i+1];ratio[i+1]=ratio[i];ratio[i]=temp1;temp2=item[i+1];item[i+1]=item[i];item[i]=temp2;}}voidmain(){inti,j;floatsum=0;clrscr();printf("\tWelcometotheBRANCH_BOUNDsystem!\n"););printf("numberofthematerials^?);scanf("%d”,&n);");printf("maximunweighoftheproblem=?");scanf("%d”,&wl);for(i=0;i{item[i]=i;printf("\n*******************\n");printf("inputitem%ddata!\n",i+1);printf("*******************\n");

”,i+1)；”,i+1)；scanf("%f”,&weight[i]);printf("value%d=?scanf("%f”,&value[i]);if((getmin())>wl)(printf("\nThereisnosolutionoftheproblem!");exit(0);}for(i=0;isum=sum+weight[i];if(sum<=wl)(printf("\nAllthematerialscanbeloaded!");exit(0);}sort();branch();printf("\n\n\nThemaximumvalueofthematerialsis%f",max_value);printf("\nincludingthefollowingmaterials\n");sum=0;for(i=0;iif(state[i]>0){sum=sum+weight[item[i]];printf("%d\n",item[i]+1);}printf("\nTheweightofthematerialsis%f",sum);Dijkstra算法Dijkstra算法算法简介Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展， 直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。算法描述(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)置集合S={2,3,...n},数组d(1)=0,d(i)=W1->i(1,i之间存在边)or+无穷大(1.i之间不存在边)在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i),d(j)+Wj->i}，转2复杂度分析Dijkstra算法的时间复杂度为O(V2)空间复杂度取决于存储方式，邻接矩阵为算法实现岸」O(nA2)输入输出格式输入格式：第1行:一个数n，代表有n个节点第2-n+1行:每行n个数，代表图的邻接矩阵，没有边相连为-1输出格式：第1行:n-1个数，分别是1号节点到2-n号节点的最短路径C++#include<fstream>#include<cstring>usingnamespacestd;constintMaxNum=1000000;//边权最大值intn;intdist[501];boolstate[501];intdata[501][501];intfindmin(){intminnode=0,min=MaxNum;for(inti=1;i<=n;i++)if((dist[i]<min)&&(!state[i])){min=dist[i];minnode=i;}returnminnode;}intmain(){ifstreamin("dijkstra.in");ofstreamout("dijkstra.out");memset(state,0,sizeof(state));in>>n;for(intp=1;p<=n;p++)for(intq=1;q<=n;q++){in>>data[p][q];if(data[p][q]==0)data[p][q]=MaxNum;}for(inti=1;i<=n;i++)dist[i]=data[1][i];state[1]=true;intdone=1;while(done<n){intnode=findmin();if(node!=0){done++;state[node]=true;for(inti=1;i<=n;i++)if((dist[i]>dist[node]+data[node][i])&&(!state[i]))dist[i]=dist[node]+data[node][i];}elsebreak;}for(intp=1;p<=n;p++){if(dist[p]==MaxNum)out<<-1;elseout<<dist[p];if(p==n)out<<endl;elseout<<"";}in.close();out.close();return0;}Pascalprogramdijkstra;varstate:array[1..100]ofboolean;data:array[1..100,1..100]oflongint;n,i,j,k,min,node:longint;beginassign(input,'dijkstra.in');assign(output,'dijkstra.out');reset(input);rewrite(output);fillchar(data,sizeof(data),0);fillchar(state,sizeof(state),0);readln(n);fori:=1tondoforj:=1tondobeginread(data[i,j]);ifdata[i,j]=0thendata[i,j]:=maxint;end;state[1]:=true;fork:=2tondobeginmin:=maxint;｛查找权值最小的点为node｝node:=1;fori:=2tondoif(data[1,i]<min)and(state[i]=false)thenbeginmin:=data[1,i];node:=i;end;｛更新其他各点的权值｝state[node]:=true;forj:=1tondoif(data[1,node]+data[node,j]<data[1,j])and(state[j]=false)thendata[1,j]:=data[1,node]+data[node,j];end;fori:=1ton-1doifdata[1,i]<>maxintthenwrite(data[1,i],'')elsewrite(-1,'');writeln(data[1,n]);close(input);close(output);end.测试样例

dijkstra算法原理详解如下图，设A为源点，求A到其他各顶点（B、C、D、E