运筹学-路径问题(名校讲义)

《运筹学-路径问题(名校讲义)》由会员分享，可在线阅读，更多相关《运筹学-路径问题(名校讲义)（28页珍藏版）》请在金锄头文库上搜索。

1、第二十六、二十七讲 路径路径问题问题问题问题 1 两点间的最短路问题 2 最小生成树问题 3 邮路问题及旅行推销员问题 1 1 两点间的最短路问题两点间的最短路问题 （1 1）例5-4已知某区的交通运输的公路分布、走向及相应费 用示于有向图5-14中。试问：卡车从v1出发经哪条路线到达v7，才能使总行程 最短？这就是网络路径问题的典型提法。 v7 0 v6 v5 v2v4 v3 v1 7 6 4 1 8 2 4 7 6 5 3 5 5 64 91385图5-141 1 两点间的最短路问题两点间的最短路问题 （2 2）1求从某点到其它点的最短路算法目前大多采用标号法，即EWDijkstra(狄克

2、斯特拉)算法， 现就介绍这种算法的思路和具体步骤。有关术语设在有向图G=（V，E）中，V=v1，v2，vn，E=e1，e2， ，em，G中每条边e= vi，vj都有一个非负实数权值W(e)， 则称G为非负赋权图（权可以表示距离、费用和时间等）。设P为图G中u至v的路径，则定义：W(P) = 为P的长度1 1 两点间的最短路问题两点间的最短路问题 （3 3）若P*为G中u至v的路径且满足：W(P)=minW(P)P为G中u至v的路径则称P*为u至v的最短路径。算法思路：设起点为v1，希求出从v1到其它顶点最短路，令d(vj)为v1至vj的 最短路长度。则(1) (2)1 1 两点间的最短路问题两

3、点间的最短路问题 （4 4）对于（2），显然有d(vj)= d(v)+ v至vj的最短路所以d(v) d(vj)，故在求d(vj)之前，应先求出d(v)。例如，在图5-14中，已求出v1至其它各点的最短距离示如方框 内（求解过程将在后面讲述），由此看出：d(v1) d(v3) d(v2) d(v4) d(v6) d(v5) d(v7)，则求解次序必为v1 v3 v7。1 1 两点间的最短路问题两点间的最短路问题 （5 5）例如，试求图5-14中v1至vj（j=2，7）的最短路径。步骤如 下：1）首先给v1一个永久性标号0，则v1A中，其它顶点标出试探 性标号为+，参见表5-4。（本节所列表中的

4、k表示阶段）。 表5-4 l(v) v kv1v2v3v4v5v6v710* +1 1 两点间的最短路问题两点间的最短路问题 （6 6）2) 利用v1得到永久性标号，计算 中各点新试探标号。l(v2)=min l(v1)+W12，l(v2)=min0+5，+=5l(v3)=min l(v1)+W13，l(v3)=min0+4，+=4同理得：l(v4)=7，l(v5)= +，l(v6)= +，l(v7)= +。取标号最小者为l(v3)=4，于是d(v3)=4，v3A，见表5-5。 表5-5l(v) v kv2v3v4v5v6v725 4*7+1 1 两点间的最短路问题两点间的最短路问题 （7 7

5、）3) v*= v3，用它计算 中各点新试探标号。l(v2)=min l(v3)+W32，l(v2)=min4+，5=5同理，l(v4)=6，l(v5)=12，l(v6)= +，l(v7)= +，继续迭代可得 表5-6。最后得出：d(v1)=0，d(v2)=5，d(v3)=4，d(v4)=6，d(v5)=9， d(v6)=8，d(v7)=13当求v1至t点的最短路径时，可从t点向前递推（见教材例5- 15。1 1 两点间的最短路问题两点间的最短路问题 （8 8）表5-6l(v) v kv1v2v3v4v5v6v710* +25 4*7+35*612+46*108+5108*+69*14713*

6、1 1 两点间的最短路问题两点间的最短路问题 （9 9）寻找最优路径的第二种方法是，把结果表与网络图结合起来， 找出哪些永久标号值之差恰等于连接边的权的顶点，然后这些 顶点之间连线即为最短路径。求最短路径第三种方法是在表格中找转折点，例如v7最短路径 为13，垂直发现14突变，横找带*点是v5，在垂直发现突变为 12， 。对于非负赋权的无向图，只需将赋权边用两个相反方向的有向 边代替即可。对于有负实数权的最短路需加以修改。（此处略）1 1 两点间的最短路问题两点间的最短路问题 （1010）2求任意两点间的最短路算法福劳德算法（不容许有负回路）。（略）矩阵相乘法i) 术语（算符）定义及算法思路其

7、中，即dij为A阵中第i行与B阵中第j列对应元素之和取极小值。1 1 两点间的最短路问题两点间的最短路问题 （1111）矩阵算法思路是：若一步到达的两点最短路长矩阵为B和已知 目前恰走l步到达的两点间最短路长为A。则知，恰走l+1步 到达的两点最短路长矩阵必DAB。例5-7求图5-18的任两点间最 短路。解 1)一步到达矩阵（vii=表 示无意义，永不走这一步， 这与福劳德算法不同）。另外，元素下标表示路径。v6 2 图5-18 v5 v4 v3 v2 v1 3 3 7 2 3 6 1 2 1 1 两点间的最短路问题两点间的最短路问题 （1212）2 2 最小生成树问题最小生成树问题 （1 1

8、）1问题的提法及现实来源例5-8 某地区共有10个村庄，村庄之间的公路联系及距离示 如教材图5-19。现计划沿公路铺设电话线，使之所有村庄之 间可以通话。试设计该区电话线网络，使总长度最短。2求解思路及算法根据该定理和树和性质，将G中的边按权值由小到大排序， 设为：避圈法（避回路法）（首先令T=）i) 初始，将e1和其端点置于图T中。2 2 最小生成树问题最小生成树问题 （2 2）ii)每步从EE（T）中选取权最小的且与T不构成回路的边 放入图T中，直到边数为n1为止。破圈法（破回路法），以图G为基础i) 在图G中，任取回路最长边。ii) 去掉回路最长边，直至无回路（或剩下n1条边）为止， 则

9、剩下的图形便是G的最小树。破圈法不一定从最长边开始，只要遵照去掉现在回路最大边 即可。最小树可能不是唯一的，只要总边权和最小即可。 3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（1 1 ） 1邮路问题问题的提出：邮递员每天从邮局取走信件，需走遍他所管理的所有街道把 信分发出去，然后返回邮局退回未送走的信件。试问，他如 何选择行走路线才能使遍历所有管理街道（有的街道可能重 复）而走的路最短？ 欧拉环游（一笔画问题）i) 有关术语若Q为连通无向图G的一条链，G的每条边在Q中恰出现一次 ，则称Q为G的欧拉链。3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（2 2 ） 闭欧拉链（

10、起、终点重合）称为欧拉环游或欧拉圈。含有欧拉环游的无向图称为欧拉图。ii) 有关判断存在性定理定理1：连通无向图G为欧拉图的充要条件为G中无奇度顶点。定理2：连通无向图G含有欧拉开链的充要条件为G中奇度点个 数恰为2个。iii) 求欧拉开链和欧拉环游的算法起始，取含欧拉链的一个奇度顶点（若为欧拉图，则任取一 点）作为起始点 。3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（3 3 ） 若已得链其中， 皆不同，且Gk=GQk连通，则选择应满足下述条件： 和 关联 不是Gk的割边，除非它是Gk与 相联的唯一边。该法寻边的过程可编口诀如下：画一条，原有图中抹一条，余下图形不断掉。 3 3

11、邮路问题及旅行推销员问题邮路问题及旅行推销员问题（4 4 ） 例如，将5-21所示的欧拉图找出欧拉环游的过程如下：v0 e1 v1 e2 v2 e3 v3 e4 v4e5 v5 e6 v3 e7 v6 e8当到v3时，不能选e7，因为e7是余下图形的割边（见图5-22）。v5 v6 v4 v0 v3 v2v1 e7 e8 e6e5 e4 e3e2 e1 图5-21v0 e8 v5 v6 v4 v3 e7 e6e5 e4 图5-223 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（5 5 ） 邮路问题（非欧拉图问题）前面所提到的邮路问题往往不满足欧拉环游（满足是特殊情 形），于是需求出这

12、种情形的最短行进路程。定义最短路程 为：w(Q*)=min w(Q)Q为G中包含G全部边的所有闭环链。 显然，若G为欧拉图，采用上面求欧拉环游方法，从邮局出发所算 出的路线即是所求。否则，G必有偶数个奇度顶点。若要通过G中全部边，必定 有的边需重复出现，则重复边的总长度反映了总行进路线长 短。因此，算法过程只比较这部分长度即可。 3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（6 6 ） i)算法思路寻找可行解：寻找图G的添加边集合F，以便构成欧拉图GQ ，GQ=GF。确定最优解：调整F，使F的权和w(F)最小，便可得出相应的 最优欧拉图。最优解判别准则为：(a) F中无平行边（不考

13、虑原边）(b)若C为G中任一回路，且知C1=eeC，有相应添加边eF，则必使ii)举例阐明求解步骤3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（7 7 ） 例5-9 求图5-25中所示的最短邮路。1)寻求初始可行解图5-25中，有四个奇度点v2，v4，v6，v8，可任意组成2对（任意图中，奇度点只能偶数个）。例如，令v2和v4，v6和v8组成2对，然后任意给出相应的2条初等链v2 v1 v8 v7 v6 v5 v4和v6 v5 v4 v3 v2 v1 v8分别解决v2，v4及v6，v8奇度问题（见图5-26）。 3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（8 8 ）显

14、然，图5-26已无奇点，故是欧拉图，得一初始可行解，其重复边 之总权和为：w(F)=2w1,2+ w2,3+ w3,4+2w4,5+2w5,6+ w6,7+ w7,8+2w8,1=515图5-25v9 v7 v8 v6 v5 v4 v3 v2 v1 4633542444 9图5-26v9 v7 v8 v6 v5 v4 v3 v2 v1 3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（9 9 ） 2) 调整附加边F，求取最优解i) 检查F中是否存在在平行边。从图5-26中看出，v2，v1，v1 ，v8，v6，v5，v4，v5中各有一对平行边，于是全从F中去 掉，得图5-27。45图5-28v9 v7 v8 v6 v5 v4 v3 v2 v1 4633542444 94634 5图5-27v9 v7 v8 v6 v5 v4 v3 v2 v1 4633542444 93 9 5 3 3 邮路问题及旅行推销员问题邮路问题及旅行推销员问题（1010）ii) 检查图5-27中，包含重复边的每一个图G回路，看是否存在 带重复边之边权和大于其它边权和。例如检查回路v2 v3 v4 v9 v2 ，知故F中掉附加边v2，v3和v3，v4，增加v4，v9和v9，v2，得 图5-28。进一步检查图5-28，发现回