最短路径问题设计

目 录第1章 绪论11.1 问题描述11.2 问题分析11.3 相关标识（名词定义）11.4 本文主要研究内容2第2章 算法设计与实现32.1 穷举法32.1.1穷举法描述32.1.2穷举法设计32.1.3 穷举法分析62.2 回溯法62.2.1 回溯法描述62.2.2 回溯法设计62.2.3 回溯法分析92.3 贪心法102.3.1 贪心法描述102.3.2 贪心法设计102.3.3 贪心法分析112.4 动态规划法112.4.1 动态规划法描述112.4.2 动态规划法设计122.4.3 动态规划法分析12第3章 实验结果分析与算法对比133.1 输入数据133.2 实验结果与分析133.3 算法分析与对比15第4章 总结与展望16参考文献17第1章 绪论1.1 问题描述最短路径问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。本文主要解决的问题是：给定带权有向图G(V, E)，对任意顶点,V（ij），求顶点到顶点的最短路径。即给定一个有向图，再给出任意2个不相邻的顶点，求2个顶点之间的最短距离。1.2 问题分析给定一个带权有向图G(V, E)中的各个顶点之间的权值，对任意输入2个顶点,V（ij），求出从到的最短路径。输入：节点数目N，邻接矩阵VRNN 约束条件： 其中， 输出（目标函数）：min Dist(,) 1.3 相关标识（名词定义）（1）时间复杂度算法的时间复杂性是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f (n)，算法的时间复杂性也因此记做T (n) = O( f (n)。因此，问题的规模n越大，算法执行时间的增长率与f (n)的增长率正相关，称作渐进时间复杂性。（2）空间复杂度空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法空间复杂度的计算公式记作：S(n)= O(f(n)，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。（3）图的基本概念图：由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V,E）。有向图：在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图。权：在图的边或弧中给出相关的数，称为权。 权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。邻接矩阵：表示一个图的常用存储表示。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。1.4 本文主要研究内容本文共分为4章，具体组织结构如下：第1章 绪论。本章主要对最短距离问题进行描述和问题进行分析，同时针对一些名词进行定义和解释。第2章 算法的设计与实现。本章主要针对最短距离问题是用穷举法、回溯法、贪心法、动态规划法实现，并对算法进行描述、设计和分析。第3章 实验结果分析与算法对比。本章主要对输入数据阐述，并对实验结果进行分析和算法分析与对比。第4章 总结与展望。总结了本文的主要工作、重要贡献以及存在的不足，提出了进一步的工作内容，并对以后的研究工作进行了展望。第2章 算法设计与实现2.1 穷举法2.1.1穷举法描述穷举搜索（Exhaustive Search Algorithm）法又称列举法，其基本思想是逐一列举问题所涉及的所有情况。穷举法常用于解决“是否存在”或“有多少种可能”等问题。穷举法的算法特点是算法简单，但是运行时所花费的时间量大，需要将问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。用穷举法实现广度优先搜索。广度优先搜索算法是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。2.1.2穷举法设计对问题使用广度优先遍历，将所有可能的结果首先保存起来，再在结果中查找最短路径的结果，打印出来。其算法流程如图2.1所示，其算法步骤可以描述为如下：（1） 从文件中读取图的节点数目、读取节点数目Npoint、起始点Start、结束点End、邻接矩阵*WeightArry。（2） 动态分配存储空间MyMarkNpoint!。（3） 初始化路径存储状态为可更新状态和第0个路径，MyMark*.state=0 MyMark*.path0=Start。（4） 依次更新MyMark的第1到（Npoint-1）路径。1） 计算每次更新存储空间数目 m = (Npoint-i-1)!；2） 依次更新j = 0到(Npoint!/m)组存储路径的节点；a. 判断存储是否可以更新，不可以则返回到2)，即判断MyMarkm*j = 0 ？；b. 计算出第i-1个路径之后的下一个路径nextPathPoint，并得到2个点之间的距离;c. 将路径更新到MyMarkm*j + k中；d. 判断nextPathPoint是否已经是最终的点，更新该组存储空间状态为完成；e. 判断距离是否不可以到达，更新该组存储空间状态为不可到达。（5） 在MyMark中查找出总代价最短的点，打印结果。其中说明如下：（1） 对2个节点之间不可到达，编程时候用MAXSIZE=1000代替。（2） 读取文件方法已经封装为一个类CfileRead，其中可以返回文件是否异常、节点数目、起始点、终点等信息。（3） 邻接矩阵*WeightArry为动态分配的二维指针，用来存放节点的权值。（4） 节点名称省略，统一用0、1、2来标示。（5） MyMarkNpoint!为动态分配的存储遍历信息的结构体，类型为mark，结构体定义为： typedefstruct markintprice;/int n;/路径数目，含头尾 int pathMAXPOINT + 1;/存储路径int states;/0:正常；-1，此路不通；1此路已经结束mark; Price：为这条路径的总代价；n：标示这条路径节点数目；path：依次存放的路径编号；states：标示这条路径的状态：1为完成了从初始点到终点、0为该路径还没有完成、-1为该路径已经不可到达。（6） 在路径更新中，起点均为iStart，然后循环往后依次增加不重复的路径，不重复指的是不与本存储中的路径冲突。实现函数： int getArryBigM(int arr, int n, int N, int M);函数功能：返回比原来arr数组中最后一个数，大于M的不重复数字。返回值：-1即没有这个数；否则返回应该填入数据。输入：arr 数组， n 数组中个数, N最大值, M为加多少。图2.1穷举法流程图（最短距离）2.1.3 穷举法分析针对本最短路径问题，穷举法实现比较简单，但是时间复杂度和空间复杂度比较大，空间复杂度为，时间复杂度为。在这里可以对算法进行如下改进：设定一个变量MinPrice=MAXSIZE存储当前代价最小值，首先判断到是否可以直接到达，可以则将其距离更新为最小代价值MinPrice，在以后的遍历中，路径的代价如果大于MinPrice则设置其状态为不可到达；若路径已经完成，且代价小于MinPrice，则MinPrice用现有完成路径代价替换。2.2 回溯法2.2.1 回溯法描述回溯法（Back Tracking Algorithm）是一种优选搜索法，按优选条件向前搜索，以达到目标。为了实现回溯， 首先需要为问题定义一个解空间， 这个解空间必须至少包含问题的一个解（可能是最优的）。然后将所有的解组织在一起形成解空间，一般的解空间的组织方法是图或树。最后在这个解空间的组织方法下可按照深度优先的方法从开始结点进行搜索。在搜索过程中，探索到某一步时发现原先的选择并不是最优或者达不到目标，就会退一步重新选择，而在回溯法中，利用限界函数可以避免移动到不可能产生解的子空间以提高算法效率。利用回溯法实现深度优先搜索。深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。2.2.2 回溯法设计针对2个顶点之间的最短路径问题使用回溯的方法解决，借用深度优先遍历的思想解决该问题，设置标记变量flag，如果标记变量为真，则打印结果，否则此2个顶点之间不可以到达。其算法流程如图2.2所示，其算法步骤可以描述为如下：（1） 从文件中读取图的节点数目、读取节点数目Npoint、起始点Start、结束点End、邻接矩阵*WeightArry。（2） 初始化结果存储变量result_old，Result_old.price = MAXSIZE，设置标记flag=0。（3） 初始化临时存储变量result_new，result_new.path* = Start，路径数目Result_new.n = 1。（4） 判断result_new.n = 1 ？不满足，则执行（5）。1） 获取满足相关条件的下一个下标iPathEnd。2） 判断 iPathEnd！=Start&约束条件？不满足则转向1），否则继续。3） 判断iPathEnd=End？，是则更新result_old = result_new；将原来结果中的代价加上当前代价；将原来结果中的节点数加1，falg=1；转向（4），否则执行下一步4）。4） 判断iPathEnd != Start？，满足则将当前路径信息添加到result_new中，result_new.n+，result_new的代价加上当前代价，转向（4）；否则继续转向5）。5） 重置路径信息，回溯。result_new.n-，result_new的代价减去后2个点之间的代价，返回（4）。（5） 判断flag=1？，不满足则转向（7）。（6） 打印结果信息。（7） 结束。其中说明如下：（1） 步骤（4）的2）中约束条件包括a.选择的节点是否可以到达；b.所选节点是否已经存在；c.当前路径代价加上现有代价总和是否小于原有最小代价。（2） result_new、result_old均为mark类型的结构体。result_new存放满足条件的路径信息；result_old存放最终的结果。（3） 在遍历的时候，首先将每一个节点初始化为Start,依次循环增加，如果增加到Start，则表示已经循环了一轮。图2.2 回溯法流程图（最短距离）2.2.3 回溯法分析（1）解空间和状态空间数假设输入的节点数为4，起点为2，终点为1，则状态空间数如图2.3所示，其解空间为(2,3,0,1)，(2,3,1)，(2,1)，（2,0,1），(2,0,3,1)，有5种可能的解。当输入规模为n时，有不超过种可能的解。图2.3 n=4时候的状态空间数（2）搜索过程从上述解空间树的根结点开始。开始时，根结点是唯一的活结点，也是当前扩展结点。根据深度优先，逐层向下进行，直到该解向量为不可行解，然后回溯到该结点的父结点，再次进行搜索。依此方法，可搜索整个解空间树。搜索结束后，找到最短距离问题的最优解。（3）搜索函数Price(i)表示搜索到第i层时的总代价，Path(i)表示搜索到第i层时的节点编号。Price(i)大于或等于当前存储的最小代价时停止搜索，转向右子数搜索；当Path(i)等于无穷时，转向右子数搜索；当Path(i)等于终点，Price(i)小于存储的最小代价时，将现有路径信息更为最小路径信息，现有代价更新为最小代价，转向右子数搜索;如果该节点只是一个中间节点，则将该节点与上一节点之间的代价加到Price(i)中，将路径更新至Path(i)中，继续向下搜索。（4）复杂度分析针对本最短路径问题，时间复杂度和空间复杂度均比穷举法小，空间复杂度为，时间复杂度为。2.3 贪心法2.3.1 贪心法描述贪心法（Greedy Algorithm）也称为贪婪算法，是一种不要求最优解，只希望得到较为满意解的方法。贪心方法常以当前情况为基础作最优选择，而不是考虑各种可能的整体情况，所以贪心方法不要回溯。贪心法一般可以快速得到满意的解，但是由于它不从整体最优上加以考虑，所得出的仅是在某种意义上的局部最优解，并且对于某些情况，可能问题实际上有解，而该算法不能找到解。利用贪心法实现Dijkstra算法。Dijkstra算法的基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。2.3.2 贪心法设计Dijkstra算法流程如图2.4所示,可描述如下，其中输入带权有向图是G=(V,E)，V= 1,2,，n，顶点v是源。c是一个二维数组，wieghtij表示边(i,j)的权。当(i,j)不属于E时，weightij是一个大数。 disti表示当前从源到顶点i的最短特殊路径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i，则这种路的最短长度是distu+weightui。如果distu+weightuidisti，则需要更新disti的值。图2.4 贪心法流程图（最短距离）其算法步骤可以简要描述如下：(1) 用带权的邻接矩阵c来表示带权有向图, weightij表示弧上的权值。设S为已知最短路径的终点的集合,它的初始状态为空集。从源点v经过S到图上其余各点vi的当前最短路径长度的初值为：disti= weight vi, vi属于V。(2) 选择vu, 使得distu=Mindisti | vi属于V-S,vj就是长度最短的最短路径的终点。(3) 修改从v到集合V-S上任一顶点vi的当前最短路径长度:如果 distu+cuj distj 则修改 distj= distu+cuj。(4) 重复操作(2),(3)共n-1次。2.3.3 贪心法分析针对本题中的最短路径问题，在测试结果中贪心法也获得了最优解，空间复杂度为，时间复杂度也。2.4 动态规划法2.4.1 动态规划法描述动态规划算法（Dynamic Programming Algorithm）是一种在数学和计算机科学中用于求解包含重叠子问题的最优化问题的方法。其基本思想是将圆问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。该算法建立在最优原则的基础上， 可以很好地解决许多用贪心方法无法解决的问题。该算法和贪心方法一样，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心方法中， 每采用一次贪心准则便做出一个不可撤回的决策， 而在动态规划中， 还要考察每个最优决策序列中是否包含一个最优子序列。所以该算法要求：无论过程的初始状态和初始决策是什么，其余的决策必须相对于初始决策所产生的状态构成一个最优决策序列。利用动态规划法实现Floyed算法。Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。2.4.2 动态规划法设计Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX)+Dis(XB)Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB)=Dis(AX)+Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。Floyd算法流程如图2.5所示：图2.5动态规划法流程图（最短距离）arrDis (i,j) : i到j的距离;arrPath (i,j): i到j的路径上i的后继点;输入带权邻接矩阵weight(i,j).（1）赋初值 对所有i,j, arrDis (i,j) weight (i,j) , path(i,j)j,k=l.（2）更新arrDis (i,j) , arrPath (i,j) 对所有i,j, 若arrDis (i,k)+ arrDis (k,j) arrDis (i,j),则 arrDis (i,j) arrDis (i,k)+ arrDis (k,j) arrPath (i,j) arrPath (i,k) , k k+1（3）重复（2)直到k=n+12.4.3 动态规划法分析Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；但是时间复杂度比较高，不适合计算大量数据。空间复杂度为，时间复杂度也。第3章 实验结果分析与算法对比3.1 输入数据输入各顶点之间的权值如图3.1所示。图3.1 输入数据邻接矩阵截图其图可以用如3.2形象的表达图3.2 测试图的结构3.2 实验结果与分析用上述测试数据验证和第二章所述算法的正确性。其实验结果截图如图3.3所示。图3.3 实验结果截图由结果可以分析知道4种算法结果一致，其最小代价均为14，路径均为0143。我们使用穷举的方法将所有可能的结果分析