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

第二十六、二十七讲 路径问题,1 两点间的最短路问题 2 最小生成树问题 3 邮路问题及旅行推销员问题,1 两点间的最短路问题 （1）,例5-4已知某区的交通运输的公路分布、走向及相应费用示于有向图5-14中。 试问：卡车从v1出发经哪条路线到达v7，才能使总行程最短？这就是网络路径问题的典型提法。,图5-14,1 两点间的最短路问题 （2）,1求从某点到其它点的最短路算法 目前大多采用标号法，即EWDijkstra(狄克斯特拉)算法，现就介绍这种算法的思路和具体步骤。 有关术语 设在有向图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 两点间的最短路问题 （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 两点间的最短路问题 （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 两点间的最短路问题 （5）,例如，试求图5-14中v1至vj（j=2，7）的最短路径。步骤如下： 1）首先给v1一个永久性标号0，则v1A中，其它顶点标出试探性标号为+，参见表5-4。（本节所列表中的k表示阶段）。,表5-4,1 两点间的最短路问题 （6）,2) 利用v1得到永久性标号，计算 中各点新试探标号。 l(v2)=min l(v1)+W12，l(v2)=min0+5，+=5 l(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-5,1 两点间的最短路问题 （7）,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 两点间的最短路问题 （8）,表5-6,1 两点间的最短路问题 （9）,寻找最优路径的第二种方法是，把结果表与网络图结合起来，找出哪些永久标号值之差恰等于连接边的权的顶点，然后这些顶点之间连线即为最短路径。 求最短路径第三种方法是在表格中找转折点，例如v7最短路径为13，垂直发现14突变，横找带*点是v5，在垂直发现突变为12， 。 对于非负赋权的无向图，只需将赋权边用两个相反方向的有向边代替即可。 对于有负实数权的最短路需加以修改。（此处略）,1 两点间的最短路问题 （10）,2求任意两点间的最短路算法 福劳德算法（不容许有负回路）。（略） 矩阵相乘法 术语（算符）定义及算法思路 其中， 即dij为A阵中第i行与B阵中第j列对应元素之和取极小值。,1 两点间的最短路问题 （11）,矩阵算法思路是：若一步到达的两点最短路长矩阵为B和已知目前恰走l步到达的两点间最短路长为A。则知，恰走l+1步到达的两点最短路长矩阵必DAB。,例5-7求图5-18的任两点间最短路。 解 1)一步到达矩阵（vii=表示无意义，永不走这一步，这与福劳德算法不同）。 另外，元素下标表示路径。,1 两点间的最短路问题 （12）,2 最小生成树问题 （1）,1问题的提法及现实来源 例5-8 某地区共有10个村庄，村庄之间的公路联系及距离示如教材图5-19。现计划沿公路铺设电话线，使之所有村庄之间可以通话。试设计该区电话线网络，使总长度最短。 2求解思路及算法 根据该定理和树和性质，将G中的边按权值由小到大排序，设为： 避圈法（避回路法）（首先令T=） i) 初始，将e1和其端点置于图T中。,2 最小生成树问题 （2）,ii)每步从EE（T）中选取权最小的且与T不构成回路的边放入图T中，直到边数为n1为止。 破圈法（破回路法），以图G为基础 i) 在图G中，任取回路最长边。 ii) 去掉回路最长边，直至无回路（或剩下n1条边）为止，则剩下的图形便是G的最小树。 破圈法不一定从最长边开始，只要遵照去掉现在回路最大边即可。最小树可能不是唯一的，只要总边权和最小即可。,3 邮路问题及旅行推销员问题（1）,1邮路问题 问题的提出： 邮递员每天从邮局取走信件，需走遍他所管理的所有街道把信分发出去，然后返回邮局退回未送走的信件。试问，他如何选择行走路线才能使遍历所有管理街道（有的街道可能重复）而走的路最短？ 欧拉环游（一笔画问题） i) 有关术语 若Q为连通无向图G的一条链，G的每条边在Q中恰出现一次，则称Q为G的欧拉链。,3 邮路问题及旅行推销员问题（2）,闭欧拉链（起、终点重合）称为欧拉环游或欧拉圈。 含有欧拉环游的无向图称为欧拉图。 ii) 有关判断存在性定理 定理1：连通无向图G为欧拉图的充要条件为G中无奇度顶点。 定理2：连通无向图G含有欧拉开链的充要条件为G中奇度点个数恰为2个。 iii) 求欧拉开链和欧拉环游的算法 起始，取含欧拉链的一个奇度顶点（若为欧拉图，则任取一点）作为起始点 。,3 邮路问题及旅行推销员问题（3）,若已得链 其中， 皆不同，且Gk=GQk连通，则选择 应满足下述条件： 和 关联 不是Gk的割边，除非它是Gk与 相联的唯一边。 该法寻边的过程可编口诀如下：画一条，原有图中抹一 条，余下图形不断掉。,3 邮路问题及旅行推销员问题（4）,例如，将5-21所示的欧拉图找出欧拉环游的过程如下： v0 e1 v1 e2 v2 e3 v3 e4 v4 e5 v5 e6 v3 e7 v6 e8 当到v3时，不能选e7，因为e7是余下图形的割边（见图5-22）。,v0,e8,3 邮路问题及旅行推销员问题（5）,邮路问题（非欧拉图问题） 前面所提到的邮路问题往往不满足欧拉环游（满足是特殊情形），于是需求出这种情形的最短行进路程。定义最短路程为：w(Q*)=min w(Q)Q为G中包含G全部边的所有闭环链。显然， 若G为欧拉图，采用上面求欧拉环游方法，从邮局出发所算出的路线即是所求。 否则，G必有偶数个奇度顶点。若要通过G中全部边，必定有的边需重复出现，则重复边的总长度反映了总行进路线长短。因此，算法过程只比较这部分长度即可。,3 邮路问题及旅行推销员问题（6）,i)算法思路 寻找可行解：寻找图G的添加边集合F，以便构成欧拉图GQ，GQ=GF。 确定最优解：调整F，使F的权和w(F)最小，便可得出相应的最优欧拉图。最优解判别准则为： (a) F中无平行边（不考虑原边） (b)若C为G中任一回路，且知 C1=eeC，有相应添加边eF，则必使 ii)举例阐明求解步骤,3 邮路问题及旅行推销员问题（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 邮路问题及旅行推销员问题（8）,显然，图5-26已无奇点，故是欧拉图，得一初始可行解，其重复边之总权和为： w(F)=2w1,2+ w2,3+ w3,4+2w4,5+2w5,6+ w6,7+ w7,8+2w8,1=51,3 邮路问题及旅行推销员问题（9）,2) 调整附加边F，求取最优解 i) 检查F中是否存在在平行边。从图5-26中看出，v2，v1，v1，v8，v6，v5，v4，v5中各有一对平行边，于是全从F中去掉，得图5-27。,3 邮路问题及旅行推销员问题（10）,ii) 检查图5-27中，包含重复边的每一个图G回路，看是否存在带重复边之边权和大于其它边权和。例如检查回路v2 v3 v4 v9 v2，知 故F中掉附加边v2，v3和v3，v4，增加v4，v9和v9，v2，得图5-28。进一步检查图5-28，发现回路中v1 v2 v9 v6 v7 v8 v1中， 故又调整F，最后结果见图5-29，总附加边长度和变为15。,3 邮路问题及旅行推销员问题（11）,2旅行推销员问题的一般概念介绍 问题的提出 旅行推销员离开原单位需遍访他所分配联系的每一座城市，然后返回。,3 邮路问题及旅行推销员问题（12）,有关术语 对于图G=(V，E) i) 至少包含图G中每个顶点一次的回路称推销员回路。求解出的最小长度回路称之为最优推销员回路。 ii) 恰恰包含图G中每个顶点一次的回路称之为哈密尔顿回路。而所求解出的最短哈密尔顿回路称为最优哈密尔顿回路。 象网络图中可能不存在欧拉环游一样，网络图亦可能不存在哈密尔顿回路。但是要判断是否存在哈密尔顿回路比判断欧拉环游的存在要复杂的多。,3 邮路问题及旅行推销员问题（13）,另外，如果邮路问题中的图G存在欧拉环游，