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

《多种方法求多段图的最短路径问题算法设计与分析课程设计报告书》由会员分享，可在线阅读，更多相关《多种方法求多段图的最短路径问题算法设计与分析课程设计报告书（14页珍藏版）》请在装配图网上搜索。

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

2、路径问题；动态规划法；分支限界法；贪心法11 / 14目 录摘 要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 参考文献101 引 言当前社会,关于最短路径的问题屡屡出现。例如在开车自驾游的一个过程中,排除其它影响因素,从一个地点到另一点,这个时候必然是希望有一条距离最短的路程来尽量减少消耗的时间以及花费的它们在模型中被称为代价,市场上对该问题的解决有很

3、大的需求,因此,这里我将讨论多段图的最短路径的问题。大二开设的数据结构课程中就包括最短路径这方面问题的讨论。当时老师介绍了分别面向单源Dijkstra算法与非单源Floyd算法两种问题的算法这是我们最早的对最短路径方面的理解,也是我们接触的比较早的关于图的问题。在这学期的算法设计与分析课程中,我们学习了很多基本的算法设计技术,蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法等,它们把以前学习的诸多方法都命名并归纳分类起来,其中有多种算法都可以用来解决最短路径问题,并且该问题作为一个图的问题,对该问题的继续探讨优化的需求很大、本文将就不同算法在解决该最短路径问题时的不同方法进行对比

4、并给出该问题在不同基础上不同的最终解决方案。由于时间的限制,本文将重点分析动态规划法下的情况,并会对图的情况加以简化、限制,最后会对其它的图做一些拓展。2 问题描述设图G=是一个带权有向连通图,如果把顶点集合V划分成k个互不相交的子集Vi2kn, 1ik,使得E中的任何一条边,必有uVi,vVi+m1ik, 1i+mk,则称图G为多段图,称sV1为源点,tVk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。多段图的最短路径问题是求从源点到终点的最小代价路径。由于多段图将顶点划分为k个互不相交的子集,所以,可以将多段图划分为k段,每一段包含顶点的一个子集。不失一般性,将多段图的顶点按

5、照段的顺序进行编号,同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n,则源点s的编号为0,终点t的编号为n-1,并且,对图中的任何一条边,顶点u的编号小于顶点v的编号。这里我们讨论的多段图是可以分段的,各段之间的关系最好是单向的,即对该有向图来说,图中是没有环的存在的。3 贪心法求解3.1 贪心法介绍贪心法是一种简单有效的方法。它在解决问题的策略上只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解,但通常能获得近似最优解。本例中利用的贪心算

6、法,是每当要选择下一个结点时,总是选择与当前结点间代价最小的点,这就叫做总是优先局部最优解,以此得到最终的解序列。这里举一个贪心法的拓展例子Dijkstra算法。Dijkstra算法是一种最短路径算法,用于计算一个节点到其它所有节点的最短路径,动态路由协议OSPF中就用到了Dijkstra算法来为路由计算最短路径。算法本身并不是按照我们的正常思维习惯,我们一般会从原点遍历所有与之相连的节点,找到最短路径,再从最短路径上的那个点遍历与之相连的所有其它点原点除外,然后依次类推。这样做虽然可以算出一个树形,但是在大多数情况下,这种算法会产生很多次优路径,也就是说非最短路径。Dijkstra算法的大概

7、过程：假设有两个集合或者说两个表,表A和表B,表A表示生成路径,表B表示最后确定的路径（1） 从原点出发,遍历检查所有与之相连的节点,将原点和这些节点存放到表A中,并记录下两节点之间的代价；（2） 将代价最小的代价值和这两节点移动到表B中其中一个是原点；（3） 把这个节点所连接的子节点找出,放入到表A中,算出子节点到原点的代价；（4） 重复第二步和第三步直到表A为空。然后根据表B中的数据算出最优树。维基百科中还有另一种说法,Dijkstra算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边,都是两个顶点所形成的有序元素对。表示从顶点u

8、到v有路径相连。我们以E所有边的集合,而边的权重则由权重函数w:E0,定义。因此,w就是从顶点u到顶点v的非负花费值。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。已知有V中有顶点s及t,Dijkstra算法可以找到s到t的最低花费路径。这个算法也可以在一个图中,找到从一个顶点s到任何其它顶点的最短路径。3.2 问题分析以起始点为中心向外层层扩展,直到扩展到终点为止。Dijstra算法边的拓展While!If存在一条从u到v的边 Ifdu+w dv= du+w;4 动态规划法求解4.1 动态规划法介绍动态规划主要用于求解以时间划分阶段的动态过程的优

9、化问题,但是一些与时间无关的静态规划如线性规划、非线性规划,可以人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。动态规划是考察问题的一种途径,或是求解某类问题的一种方法。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比其它方法求解更为方便。动态规划法设计算法一般分成三个阶段： 划分子问题：将原问题分解为若干个子问题, 每个子问题对应一个决策阶段,并且子问题之间具有重叠关系； 确定动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式,这是动态规划

10、法的关键； 填写表格：设计表格,以自底向上的方式计算各个子问题的解并填表,实现动态 原问题的解 原问题 填 表子问题1子问题2子问题n规划过程。4.2 问题分析设数组costn存储最短路径长度,costj表示从源点s到顶点j的最短路径长度,数组pathn记录状态转移,pathj表示从源点到顶点j的路径上顶点的前一个顶点,动态规划法求解多段图的最短路径问题的算法如下：输入：多段图的代价矩阵输出：最短路径长度及路径1. 循环变量j从1n-1重复下述操作,执行填表工作： 1.1 考察顶点j的所有入边,对于边E： 1.1.1 costj=mincosti+cij; 1.1.2 pathj=使costi

11、+cij最小的i; 1.2 j+;2. 输出最短路径长度costn-1;3. 循环变量i=pathn-1,循环直到pathi=0： 3.1 输出pathi; 3.2 i=pathi;第一部分是依次计算各个顶点到终点的最短路径,由两层嵌套的循环组成,外层循环执行n-1次,内层循环对所有入边进行计算,并且在所有循环中,每条入边只计算一次。假定图的边数为m,则这部分的时间性能是O；第二部分是输出最短路径经过的顶点,设多段图划分为k段,其时间性能是O。所以,该算法的时间复杂性为O。 5 分支限界法求解5.1 分支限界法介绍分支限界法按广度优先策略搜索问题的解空间树,在搜索过程中,对待处理的结点根据限界

12、函数估算目标函数的可能取值,从中选取使目标函数取得极值极大或极小的结点优先进行广度优先搜索,从而不断调整搜索方向,尽快找到问题的解。5.2 问题分析讨论当用分支限界法用来解决多段图路径问题的过程：首先对该多段图应用贪心法求得近似解,并算出其代价路径。将其作为多段图最短路径问题的上界。而把每一段最小的代价相加,可以得到一个非常简单的下界。于是,就可以得到了目标函数的一个大致的范围。由于多段图将顶点划分为k个互不相交的子集,所以,多段图划分为k段,一旦某条路径的一些段被确定后,就可以并入这些信息并计算部分解的目标函数值的下界。一般情况下,对于一个正在生成的路径,假设已经确定了i段1ik,其路径为,

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

14、p；2将待处理结点表PT初始化为空；3for i=1; ixi=0;4i=1; u=0; /求解第i段 5while =1 5.1 对顶点u的所有邻接点v 5.1.1 计算目标函数值lb; 5.1.2 若lb=up,则将i,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 u=表PT中lb最小的结点的v值； 5.5 i=表PT中lb最小的结点的

15、i值；i+;6 程序清单6.1 源代码#includeconst int N = 20;const int MAX = 1000;int arcNN; int Backpath;int creatGraph;int creatGraphint i, j, k;int weight;int vnum, arcnum;cout输入顶点的个数和边的个数：vnumarcnum;for i = 0; i for j = 0; j arcij = MAX;for k = 0; k coutijweight;arcij = weight;return vnum;int Backpathint i, j, t

16、emp;int costN;int pathN;fori = 0; i costi = MAX;pathi = -1;cost0 = 0;forj = 1; j for= 0; i-if arcij + costi costj = arcij + costi;pathj = i;coutn-1; i = n-1;while = 0cout-pathi;i = pathi;coutendl;return costn-1;int mainint n = creatGraph;int pathLen = Backpath;cout最短路径的长度是：pathLenendl;return 0;6.2 结

17、果截图7 结果分析（1） 贪心法、动态规划法和分支限界法都可以用来解决多段最短路径问题,然而在这种情况相比之下,贪心法的运算效率比较高,因为它不像另外两种方法一样,需要涉及到许多的点。可以看到,动态规划法由于需要填表,并有一个相关的迭代问题,它几乎涉及了所有的点；而分支限界法,它通过贪心法设置的上下限,并以它们为依据进行剪枝,减少了许多的运算量。而贪心法,访问了最少的点。（2） 就结果准确性来看,就本题例子来看,贪心法结果为0 2 4 7 9,路径的代价为20；动态分配法采取的路径为：0 3 5 8 9,路径的代价为16；而分支限界法,结果为0 3 5 8 9,路径的代价为16。可以看出,在这

18、个方面,动态分配法和分支限界法都达到了预期的结果,相比直线,贪心法的误差就比较大了。由以上的讨论,我们可以看出分支限界法的综合性能比较好,它和动态规划法在解决多段最短路径问题时都可以得到正确解,而贪心法虽然可以省时间与空间,但结果不准确是它的缺点。各方法都是有利有弊的。因此在选择方法时,还应当根据实际情况。当只需要大概的一个解时,当然是要用省时省力的贪心法；如果对结果又比较高的要求的话,就要采取动态规划法或分支限界法。dijkstra算法的明显优点就是它的多用性,它可以求任意一点到其它某一点的距离,但是它访问的数据量很大,几乎要访问所有的边相对于贪心法而言,因此这里来说,在单纯的解决多段最短路

19、径问题时,它们的功能都差不多,而在解决其它较复杂的图时,Dijkstra算法有明显的优越性,但当然,作为贪心法的一种,它的结果的准确性不是那么的高。Dijkstra算法在本质上为贪心算法,每一步的选择为当前步的最优,复杂度为O。动态规划法是可以看作是对分支限界法的改进。其实,它们各有各的优缺点,可以尝试将它们混合起来用,扬长避短,设置范围,并且过程中对肯定不会是最后结果的数据剪枝。这样就可以提高运行速率了。8 课程体会算法分析与设计是一门非常重要的课程。很多问题的解决,程序的编写都要依赖它,在软件还是面向过程的阶段,就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极

20、大帮助的,它可以培养我们养成思考分析问题,解决问题的能力。作为IT行业学生,学习算法无疑会增强自己的竞争力,修炼自己的内功。谢谢老师的指导,学习算法分析与设计使我对软件基础知识中算法的地位有了充分的了解,虽然课程结束了,但我依然还会继续学习算法分析与设计,以后我将充分利用所学到我实际的开发项目中。9 参考文献1王红梅,胡明.算法设计与分析第二版.北京：清华大学出版社.2013.42严蔚敏, 吴伟民. 数据结构北京：清华大学出版社.20103 余祥宣,催国华,邹海明.计算机算法基础第三版MXX：华中科技大学出版社.20064卜月华.图论及其应用.XX：东南大学出版社.2000班级学号姓名大作业题

21、目多种方法解决多段图的最短路径问题评阅点评分标准细则分值实得分算法设计与实现40分正确实现本程序所需全部功能,算法设计正确合理且有一定创新,结果正确40分实现所需功能,算法正确,结果正确30分基本实现所需功能,结果正确15分有明显重大错误5分无法实现程序功能0分算法分析20分算法分析全面、详细、正确20分算法分析比较全面、正确15分算法分析基本正确10分算法分析有明显错误5分程序可读、可维护性10分程序可读性好、逻辑清晰,程序完整,可维护性好10分程序可读、可维护8分基本可读可维护5分逻辑混乱、不可读0分报告质量20分报告规范,符合技术用语要求,行文流畅,层次清晰20分报告书写基本规范,符合技术用语要求,文理较通畅15分结构较合理,层次较清楚,基本符合要求10分结构混乱,文不对题目,或者有明显抄袭现象5分设计验收好10分；通过8分；基本合格6分10分总 分大作业成绩评定表 教师签名：