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

学号：《算法设计与分析B》大作业题目多种方法解决多段图的最短路径问题学院计算机科学与技术学院专业软件工程班级姓名指导教师2014年12月26日武汉理工大学《算法设计与分析》课程设计II多种方法解决多段图的最短路径问题摘要多段图的最短路径问题是求从源点到终点的最小代价路径。本文主要描述的是分别用动态规划法、贪心法和分支限界法来解决多段图最短路径问题时的情况。文章首先阐述了各个方法的原理，主要的思路是通过输入一组数据，比较三者的输出结果的准确性以及运行时间，以之为基础来分析、讨论三者的性能区别。文章最后讲述了若这几种方法运行到有向图中的情况，几种方法的对比和它们比较适应的使用情况的讨论，并给出了自己的建议。关键字：多段图最短路径问题；动态规划法；分支限界法；贪心法武汉理工大学《算法设计与分析》课程设计III目录摘要.................................................................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参考文献.............................................................10武汉理工大学《算法设计与分析》课程设计11引言当前社会，关于最短路径的问题屡屡出现。例如在开车自驾游的一个过程中，排除其它影响因素，从一个地点到另一点，这个时候必然是希望有一条距离最短的路程来尽量减少消耗的时间以及花费的（它们在模型中被称为代价），市场上对该问题的解决有很大的需求，因此，这里我将讨论多段图的最短路径的问题。大二开设的《数据结构》课程中就包括最短路径这方面问题的讨论。当时老师介绍了分别面向单源（Dijkstra算法）与非单源（Floyd算法）两种问题的算法——这是我们最早的对最短路径方面的理解，也是我们接触的比较早的关于图的问题。在这学期的《算法设计与分析》课程中，我们学习了很多基本的算法设计技术，蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法等，它们把以前学习的诸多方法都命名并归纳分类起来，其中有多种算法都可以用来解决最短路径问题，并且该问题作为一个图的问题，对该问题的继续探讨优化的需求很大、本文将就不同算法在解决该最短路径问题时的不同方法进行对比并给出该问题在不同基础上不同的最终解决方案。由于时间的限制，本文将重点分析动态规划法下的情况，并会对图的情况加以简化、限制，最后会对其它的图做一些拓展。2问题描述设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一条边(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。多段图的最短路径问题是求从源点到终点的最小代价路径。由于多段图将顶点划分为k个互不相交的子集，所以，可以将多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。这里我们讨论的多段图是可以分段的，各段之间的关系最好是单向的，即对该有向图来说，图中是没有环的存在的。武汉理工大学《算法设计与分析》课程设计23贪心法求解3.1贪心法介绍贪心法是一种简单有效的方法。它在解决问题的策略上只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。本例中利用的贪心算法，是每当要选择下一个结点时，总是选择与当前结点间代价最小的点，这就叫做总是优先局部最优解，以此得到最终的解序列。这里举一个贪心法的拓展例子Dijkstra算法。Dijkstra算法是一种最短路径算法，用于计算一个节点到其它所有节点的最短路径，动态路由协议OSPF中就用到了Dijkstra算法来为路由计算最短路径。算法本身并不是按照我们的正常思维习惯，我们一般会从原点遍历所有与之相连的节点，找到最短路径，再从最短路径上的那个点遍历与之相连的所有其它点（原点除外），然后依次类推。这样做虽然可以算出一个树形，但是在大多数情况下，这种算法会产生很多次优路径，也就是说非最短路径。Dijkstra算法的大概过程：假设有两个集合或者说两个表，表A和表B，表A表示生成路径，表B表示最后确定的路径（1）从原点出发，遍历检查所有与之相连的节点，将原点和这些节点存放到表A中，并记录下两节点之间的代价；（2）将代价最小的代价值和这两节点移动到表B中（其中一个是原点）；（3）把这个节点所连接的子节点找出，放入到表A中，算出子节点到原点的代价；（4）重复第二步和第三步直到表A为空。然后根据表B中的数据算出最优树。维基百科中还有另一种说法，Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负武汉理工大学《算法设计与分析》课程设计3花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e.最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其它顶点的最短路径。3.2问题分析以起始点为中心向外层层扩展，直到扩展到终点为止。Dijstra算法（边的拓展）{While（!(每一个d[v]==最短路径)）If（存在一条从u到v的边）If(d[u]+w(u,v)d[v])d[v]=d[u]+w(u,v);}4动态规划法求解4.1动态规划法介绍动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划是考察问题的一种途径，或是求解某类问题的一种方法。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比其它方法求解更为方便。动态规划法设计算法一般分成三个阶段：(1)划分子问题：将原问题分解为若干个子问题，每个子问题对应一个决策阶段，并且子问题之间具有重叠关系；(2)确定动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式(即动态规划函数)，这是动态规划法的关键；(3)填写表格：设计表格，以自底向上的方式计算各个子问题的解并填表，实现动态武汉理工大学《算法设计与分析》课程设计4规划过程。4.2问题分析设数组cost[n]存储最短路径长度，cost[j]表示从源点s到顶点j的最短路径长度，数组path[n]记录状态转移，path[j]表示从源点到顶点j的路径上顶点的前一个顶点，动态规划法求解多段图的最短路径问题的算法如下：输入：多段图的代价矩阵输出：最短路径长度及路径1.循环变量j从1~n-1重复下述操作，执行填表工作：1.1考察顶点j的所有入边，对于边(i,j)∈E：1.1.1cost[j]=min{cost[i]+cij};1.1.2path[j]=使cost[i]+cij最小的i;1.2j++;2.输出最短路径长度cost[n-1];3.循环变量i=path[n-1]，循环直到path[i]=0：3.1输出path[i];3.2i=path[i];第一部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有入边进行计算，并且在所有循环中，每条入边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第二部分是输出最短路径经过的顶点，原问题的解原问题……填表子问题1子问题2子问题n武汉理工大学《算法设计与分析》课程设计5设多段图划分为k段，其时间性能是O(k)。所以，该算法的时间复杂性为O(n+k)。5分支限界法求解5.1分支限界法介绍分支限界法按广度优先策略搜索问题的解空间树，在搜索过程中，对待处理的结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。5.2问题分析讨论当用分支限界法用来解决多段图路径问题的过程：首先对该多段图应用贪心法求得近似解，并算出其代价路径。将其作为多段图最短路径问题的上界。而把每一段最小的代价相加，可以得到一个非常简单的下界。于是，就可以得到了目标函数的一个大致的范围。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，一旦某条路径的一些段被确定后，就可以并入这些信息并计算部分解的目标函数值的下界。一般情况下，对于一个正在生成的路径，假设已经确定了i段（1≤i≤k），其路径为(r1,r2,…,ri,ri+1)，此时，该部分解的目标函数值的计算方法即限界函数如下：应用分支限界法同样求解多段图的最短路径问题，具体的搜索过程是这样进行的，首先考虑根节点，根据限界函