最短路径法.docx

最短路径法 实际中有关最短路径问题都是以带权图为主；首先假设有以下图论模型: 在带权图G=（V，E）中，若顶点 Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。 对于非带权图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。 最短路径问题可以分为两类：一是：求从某个顶点（源点）到其它顶点（终点）的最短路径；二是：另一类是求图中每一对顶点间的最短路径。 其中以第一类问题比较多；比如常见的连连看游戏中对两个相同的元素之间进行连线就属于这类问题； 解决图论相关问题的第一步就是对图进行数据表示：采用的方法是利用邻接矩阵，存放任意两点间的数据（如距离、费用、时间等）；详细介绍请查看百度百科 最短路径相关算法有：宽度优先搜索，启发式搜索，等代价搜索法，宽度搜索+剪枝，动态规划法；下面我们采用最常见的实际应用来讲述这些算法的应用： 例子：假设A、B、C、D、E各个城市之间旅费如下图红色数字所示。某人想从城市A出发游览各城市一遍，而所用旅费最少，试编程输出结果。一：宽度优先搜索 应该来说宽度优先搜索并不是解决最短路径的优秀算法；只是为其他的算法做一个铺垫； 算法流程如下： 1、 从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其旅费； 2、 再次由AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然由AD可以展开得到ADB、ADC、ADE，由AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其旅费； 3、 再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED、AEDB、AEDC，每个结点也需记录下其旅费； 4、 再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、AEDBC、AEDCB，每个结点也需记录下其旅费； 5、 到此，所有可能的结点均已展开，而第五层结点中旅费最少的那个就是题目的解了。 从上面的描述可见，宽度优先搜索算法是一个耗时的算法；并非是用来求解最短路径或者最优化问题的方法；只能算的上是一个枚举所有路径的方法；二： 启发式搜索 在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。 这种算法最关键的问题就是如何确定估价函数，估价函数越准，则能越快找到答案。这种算法实现起来并不难，只不过难在找准估价函数，大家可以自已找相关资料学习和思考。三：等代价搜索法 等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是启发式搜索的一种简化版本。也是比较推荐的一种方法； 它的大体思路是： 1、 从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其旅费（括号中的数字）； 2、 把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开； 3、 再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开； 4、 再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点，； 5、 每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。 四：宽度优先搜索+剪枝（2009-8-19修改） 对纯宽度优先搜索算法的学习可知他的缺点是完全遍历；对在搜索过程明知不是最优解的分支同样进行遍历；造成大量的耗时；所以下面介绍利用利用剪枝的方法来终止搜索过程中有些搜索过程；我们的原理是：假如在搜索时已经搜出从起点A到点B的某一条路径的长度是X，那么我们就可以知道，从A到B的最短路径长度必定X，因此，其他从A到B的长度大于或等于X的路径可以一律剔除。 我们的伪代码的格式如下： 1.定义一个数组h1.n；其中n表示节点数，hi表示从起点到节电i的最短路径长度 2.初始化：将起始节点start放入一个队列中；并hstart=0;histart=一个大整数； 3.循环过程： do 取出对头的节点赋值给temp; while temp有相邻的节点没有被扩展 temp扩展出来的新节点 new if(htemp+距离temp-new new; while(队列空)； 最后最短距离就是h1.n最小值了啊五 ：动态规划法（2009-8-19修改） 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但这种方法只适用有向无回路图；因此如果存在回路，动态规划的方法就不适用了； 动态规划的算法表达式为f(n)=min(f(n-1)+x1,f(n-2)+x2)；其表达式和后面介绍的递归有相似之处；大家对比着的看； 下面以一个例子来讲述程序的实现； 1.图1因为存在回路而不能用动态规划。而图2是无回路的，所以可以用动态规划解决 2.对左图拓扑排序，得到的序列是A、B、D、C、E。(这步是动态规划必须很重要的一步；请参加拓扑排序概念) 3. 设F(E)表示从A到E的最短路径长度，然后按照拓扑序列的先后顺序进行动态规划： F(A)=0 F(B)=min F(A) +3=3 F(D)=min F(A)+8, F(B)+2 =5 F(C)=min F(B)+9, F(D)+5 =10 F(E)=min F(D)+1, F(C)+4 =6 总式子是：F(i)=min F(k)+dis(i,k) ，k与i相连，且在拓扑序列中，k在i之前。六：迭代法（2009-8-19修改） 该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。即： Dij = min Dij , Dik+Dkj ，1=k=n。 这样，我们就找到了一个类似动态规划的表达式，只不过这里我们不把它当作动态规划去处理，而是做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到A到E的最短路径。 算法流程如下： Di表示从起点到i的最短路的长度，g是邻接矩阵，s表示起点； 1、Di:=gs,i (1=i=n)； 2、 do c=false; for(j=1;j=n;j+) for(k=1;kDk+gk,j) Dj:= Dk+gk,j; c:=true; while(!c); 这种算法是产生这样一个过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应的两点间的最短距离。七：标点法（2009-8-22修改） 应该来说标点法是那么多方法中最一目了然的方法；所以这里我就把基本的方法讲一下； 从标点法的分析上来讲，我们可以假设有一个坐标轴；搜索过程为： 1. 以起始点A为坐标轴零点；展开与其相邻的点，并在坐标轴上标出；如图 2. 从图可知，C点离起点A最近，因此可以断定C点一定是由A直接到C点这条路径是最短的（因为A、C两点间没有其它的点，所以C点可以确定是由A点直接到达为最短路径）。因而就可以以已经确定的C点为当前展开点，展开与C点想连的所有点A、B、D、E。 并标出 3. 由数轴可见，A与A点相比，A点离原点近，因而保留A点，删除A点，相应的，B、B点保留B点，D、D保留D，E、E保留E，得到下图： 4.