多种方法求多段图的最短路径问题算法设计与分析课程设计

1、学号：算法设计与分析B 大作业题 目 学 院 专 业 班 级 姓 名 指导教师多种方法解决多段图的最短路径问题计算机科学与技术学院软件工程2014 年12 月26 日武汉理工大学算法设计与分析课程设计多种方法解决多段图的最短路径问题摘要多段图的最短路径问题是求从源点到终点的最小代价路径。本文主要描述的是分别用 动态规划法、贪心法和分支限界法来解决多段图最短路径问题时的情况。文章首先阐述了 各个方法的原理，主要的思路是通过输入一组数据，比较三者的输出结果的准确性以及运 行时间，以之为基础来分析、讨论三者的性能区别。文章最后讲述了若这几种方法运行到 有向图中的情况，几种方法的对比和它们比较适应的使

2、用情况的讨论，并给出了自己的建 议。关键字：多段图最短路径问题；动态规划法；分支限界法；贪心法II武汉理工大学算法设计与分析课程设计目录摘要 II1引言 12问题描述 13贪心法求解 23.1贪心法介绍 23.2问题分析 34动态规划法求解 34.1动态规划法介绍 34.2问题分析 45分支限界法求解 55.1分支限界法介绍 55.2问题分析 56程序清单 66.1源代码 66.2结果截图 97结果分析 98课程体会 109参考文献 10iii武汉理工大学算法设计与分析课程设计1引言当前社会，关于最短路径的问题屡屡出现。例如在开车自驾游的一个过程中，排除其 它影响因素，从一个地点到另一点，这个

3、时候必然是希望有一条距离最短的路程来尽量减 少消耗的时间以及花费的（它们在模型中被称为代价），市场上对该问题的解决有很大的 需求，因此，这里我将讨论多段图的最短路径的问题。大二开设的数据结构课程中就包括最短路径这方面问题的讨论。当时老师介绍了 分别面向单源（Dijkstra算法）与非单源（Floyd算法）两种问题的算法这是我们最早的对最短路径方面的理解，也是我们接触的比较早的关于图的问题。在这学期的算法设计与分析课程中，我们学习了很多基本的算法设计技术，蛮力 法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法等，它们把以前学习的 诸多方法都命名并归纳分类起来，其中有多种算法都可以用来解

4、决最短路径问题，并且该 问题作为一个图的问题，对该问题的继续探讨优化的需求很大、本文将就不同算法在解决 该最短路径问题时的不同方法进行对比并给出该问题在不同基础上不同的最终解决方案。 由于时间的限制，本文将重点分析动态规划法下的情况，并会对图的情况加以简化、限制,最后会对其它的图做一些拓展。2问题描述设图G=（V, E）是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集 Vi （2< k< n, Ki< k），使得 E 中的任何一条边（u, v），必有 u Vi，v Vi+m （1< i vk, 1 v i+m < k ），贝U称图G为多段图，称s V

5、1为源点，t Vk为终点。多段图的最短路径问 题是求从源点到终点的最小代价路径。多段图的最短路径问题是求从源点到终点的最小代 价路径。由于多段图将顶点划分为k个互不相交的子集，所以，可以将多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段 内顶点的相互顺序无关紧要。假设图中的顶点个数为n,贝U源点s的编号为0,终点t的编号为n-1，并且，对图中的任何一条边（u, v），顶点u的编号小于顶点v的编号。这里我们讨论的多段图是可以分段的，各段之间的关系最好是单向的，即对该有向图 来说，图中是没有环的存在的3贪心法求解3.1贪心法介绍贪心法是一种简单有效

6、的方法。它在解决问题的策略上只根据当前已有的信息就做出 选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种 局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。本例中利用的贪心算法，是每当要选择下一个结点时，总是选择与当前结点间代价最 小的点，这就叫做总是优先局部最优解，以此得到最终的解序列。这里举一个贪心法的拓 展例子Dijkstra算法。Dijkstra算法是一种最短路径算法，用于计算一个节点到其它所有节点的最短路径，动态路由协议OSPF中就用到了 Dijkstra算法来为路由计算最短路径。算

7、法本身并不是按照我们的正常思维习惯，我们一般会从原点遍历所有与之相连的节 点，找到最短路径，再从最短路径上的那个点遍历与之相连的所有其它点（原点除外），然后依次类推。这样做虽然可以算出一个树形，但是在大多数情况下，这种算法会产生很 多次优路径，也就是说非最短路径。Dijkstra算法的大概过程：假设有两个集合或者说两个表，表 A和表B，表A表示生成路径，表B表示最后确 定的路径（1） 从原点出发，遍历检查所有与之相连的节点，将原点和这些节点存放到表A中， 并记录下两节点之间的代价；（2） 将代价最小的代价值和这两节点移动到表B中（其中一个是原点）；（3） 把这个节点所连接的子节点找出，放入到表

8、A中，算出子节点到原点的代价；（4） 重复第二步和第三步直到表 A为空。然后根据表B中的数据算出最优树。维基百科中还有另一种说法，Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点So我们以V表示G中所有顶点的集合。 每一个图中的边，都是两 个顶点所形成的有序元素对。（u,v）表示从顶点u到v有路径相连。我们以E所有边的集合， 而边的权重则由权重函数 w: E 0, g定义。因此，w（u,v）就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是 该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstr

9、a算法可以找到s到t的最低花费路径(i.e.最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其它 顶点的最短路径。3.2问题分析以起始点为中心向外层层扩展，直到扩展到终点为止。Dijstra算法(边的拓展)While(!(每一个dv=最短路径)If (存在一条从u到v的边)lf(du+w(u,v)<dv)dv= du+w(u,v);4动态规划法求解4.1动态规划法介绍动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关 的静态规划(如线性规划、非线性规划)，可以人为地引进时间因素，把它视为多阶段决 策过程，也可以用动态规划方法方便地求解。动态规划是考察问

10、题的一种途径，或是求解某类问题的一种方法。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛 的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规 划方法比其它方法求解更为方便。动态规划法设计算法一般分成三个阶段：(1) 划分子问题：将原问题分解为若干个子问题，每个子问题对应一个决策阶段，并且子问题之间具有重叠关系；(2) 确定动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式(即动态规划函数)，这是动态规划法的关键；(3) 填写表格：设计表格，以自底向上的方式计算各个子问题的解并填表，实现动态设数组costn存储最短路径长度，c

11、ostj表示从源点s到顶点j的最短路径长度，数组 pathn记录状态转移，pathj表示从源点到顶点j的路径上顶点的前一个顶点，动态规划法 求解多段图的最短路径问题的算法如下：输入：多段图的代价矩阵输出：最短路径长度及路径1. 循环变量j从1n-1重复下述操作，执行填表工作：1.1考察顶点j的所有入边，对于边(i, j) E：1.1.1 costj=mi ncosti+cij;1.1.2 pathj=使 costi+cij 最小的 i;1.2 j+;2. 输出最短路径长度costn-1;3. 循环变量i=pathn-1，循环直到pathi=0 :3.1 输出 pathi;3.2 i=pathi

12、;第一部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环 执行n-1次，内层循环对所有入边进行计算，并且在所有循环中，每条入边只计算一次。 假定图的边数为m,则这部分的时间性能是 0(m);第二部分是输出最短路径经过的顶点，设多段图划分为k段，其时间性能是0(k)。所以，该算法的时间复杂性为 0(n+k)。5分支限界法求解5.1分支限界法介绍分支限界法按广度优先策略搜索问题的解空间树，在搜索过程中，对待处理的结点根 据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值(极大或极小)的结 点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。5.2问题分析讨

13、论当用分支限界法用来解决多段图路径问题的过程:首先对该多段图应用贪心法求得近似解，并算出其代价路径。将其作为多段图最短路 径问题的上界。而把每一段最小的代价相加，可以得到一个非常简单的下界。于是，就可 以得到了目标函数的一个大致的范围。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为 k段，一旦某条 路径的一些段被确定后，就可以并入这些信息并计算部分解的目标函数值的下界。一般情 况下，对于一个正在生成的路径，假设已经确定了 i段(伯眾)，其路径为(ri,禺 ,i, ri+i)， 此时，该部分解的目标函数值的计算方法即限界函数如下：lbminri i ,vpEcri ivpk第j段的

14、最短边应用分支限界法同样求解多段图的最短路径问题，具体的搜索过程是这样进行的，首先考虑根节点，根据限界函数算出目标函数的值，这里每种情况下的目标函数值下界都要 算出来并且加以比较，下界的计算方法为除了加上选定点与初始点之间的距离外，以后的 第一个点选择一选定点为初始点到下段最小代价的路径，以后的段与段之间的代价都按它 们之间最小的代价来计算。这样再加上根节点与初始阶段之间的最小代价，就得到这种情 况下的解了。在得到的代价中，找出最小的代价，并以之为初始结点循环往下做，直到到 达目标结点。算法如下:1 根据限界函数计算目标函数的下界 dow n；采用贪心法得到上界up；2 将待处理结点表PT初始

15、化为空；3. for (i=1; i<=k; i+)xi=0;4. i=1; u=0;/求解第 i 段5. while (i>=1)5.1对顶点u的所有邻接点v5.1.1计算目标函数值lb;5.1.2 若 lb<=up，则将 i,<u,v>,lb 存储在表 PT 中；5.2如果i= =k-1且叶子结点的lb值在表PT中最小，则输出该叶子结点对应的最优解；5.3否则，如果i= =k-1且表PT中的叶子结点的lb值不是最小，则5.3.1 up=< PT中的叶子结点最小的lb值；5.3.2将表PT中目标函数值超出up的结点删除；5.4 口=表PT中lb最小的结点的

16、v值；5.5 i=表PT中lb最小的结点的i值；i+;6程序清单6.1源代码#in clude<iostream.h> const int N = 20; const int MAX = 1000; int arcNN;int Backpath(i nt n);int creatGraph();int creatGraph()int i, j, k;int weight;int vnum, arcnum;"<<e ndl;coutvv"输入顶点的个数和边的个数：cin>>vnum >>arc num;for (i = 0; i

17、 < vnum; i+)for (j = 0; j < vnu m; j+)arcij = MAX;for (k = 0; k < arcnum; k+)coutvv"输入边的两个顶点和权值:cin»i> >j>>weight;arcij = weight;return vnum;int Backpath(i nt n)int i, j, temp;int costN;in t pathN;for(i = 0; i < n; i+)costi = MAX;pathi = -1;cost0 = 0;for(j = 1; j &l

18、t; n; j+)for(i = j - 1; i >= 0; i-)if (arcij + costi < costj)costj = arcij + costi; pathj = i;cout< <n-1;i = n-1;while (pathi >= 0)cout<v"v-"vvpathi;i = pathi;cout«e ndl;return cost n-1;int mai n()int n = creatGraph();int pathLe n = Backpath( n);cout«"最短路径的

19、长度是："vvpathLe n<<e ndl;return 0;6.2纟口果截图坪：窑料方伝求寡段塁氏最盪空径二筈飞DebugV程存实反于1 42 23 34 95 84 65 7 £ B5 46 77 58 67 86 67 68 59 79 30 001122 2 3-344S56 67ft- + 1 *- «- MX- £« ¥ £ ja/ -IJ -IJ- -JI - y -IJ- -JJ- -7 R/ 一7 - -Jr -/口口 u 口卫 D 口口 口 口口口 D 口口 口口口亠叫=一气Lr 4r* *

20、Lr 4 L, 口气卜 -r 上r a,rQ L, -!上-% 上 一-E>r>r a, 一h4 r.临 n1 o c>=tD占苦苦心点占笞苦苦笞M点点点10m点点占心点点 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶E度y TTTTTTTTTTTTXITTT Fn- nH- nMJ- - nMJ- - -JH- - nn- - nH- PM -LUMJ- -hMd- _hu- - _Jn- - nH- - nn- - nM FMJ- - nH- 3 Lnu- n Mnn.- n u n: nn rr. rT. nHn.- Mnn.l nu n“ rr T rr. . Hu.- nn

21、“ rr “ J 1 VJJ r _5i3r ff 一 JB 卯 LanVLJvlmvlmvluu=.-ct"“.-it- :vljV rnj.VLJ" <z工 n i._3- 3- CJ 边边边边边边边理边边边边边势边边J路S90 _一 £ 一 S 一 e-區一7结果分析（1）贪心法、动态规划法和分支限界法都可以用来解决多段最短路径问题，然而在这种情况相比之下，贪心法的运算效率比较高，因为它不像另外两种方法一样，需要涉及到 许多的点。可以看到，动态规划法由于需要填表，并有一个相关的迭代问题，它几乎涉及 了所有的点；而分支限界法，它通过贪心法设置的上下限，并

22、以它们为依据进行剪枝，减 少了许多的运算量。而贪心法，访问了最少的点。（2）就结果准确性来看，就本题例子来看，贪心法结果为0 2 4 7 9,路径的代价为20； 动态分配法采取的路径为：0 3 5 8 9,路径的代价为16;而分支限界法，结果为0 3 5 8 9, 路径的代价为16。可以看出，在这个方面，动态分配法和分支限界法都达到了预期的结果， 相比直线，贪心法的误差就比较大了。由以上的讨论，我们可以看出分支限界法的综合性能比较好，它和动态规划法在解决多段最短路径问题时都可以得到正确解，而贪心法虽然可以省时间与空间，但结果不准确 是它的缺点。各方法都是有利有弊的。因此在选择方法时，还应当根据

23、实际情况。当只需 要大概的一个解时，当然是要用省时省力的贪心法；如果对结果又比较高的要求的话，就 要采取动态规划法或分支限界法。dijkstra算法的明显优点就是它的多用性，它可以求任意 一点到其它某一点的距离，但是它访问的数据量很大，几乎要访问所有的边（相对于贪心 法而言），因此这里来说，在单纯的解决多段最短路径问题时，它们的功能都差不多，而 在解决其它较复杂的图时，Dijkstra算法有明显的优越性，但当然，作为贪心法的一种，它 的结果的准确性不是那么的高。Dijkstra算法在本质上为贪心算法，每一步的选择为当前步 的最优，复杂度为0（n*n）。动态规划法是可以看作是对分支限界法的改进。其实，它们各有各的优缺点，可以尝试将它们混合起来用，扬长避短，设置范围，并 且过程中对肯定不会是最后结果的数据“剪枝”。这样就可以提高运行速率了。8课程体会算法分析与设计是一门非常重要的课程。很多问题的解决，程序的编写都要依赖它， 在软件还是