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

第二十六 二十七讲路径问题 1两点间的最短路问题 2最小生成树问题 3邮路问题及旅行推销员问题 1两点间的最短路问题 1 例5 4 已知某区的交通运输的公路分布 走向及相应费用示于有向图5 14中 试问 卡车从v1出发经哪条路线到达v7 才能使总行程最短 这就是网络路径问题的典型提法 图5 14 1两点间的最短路问题 2 1 求从某点到其它点的最短路算法目前大多采用标号法 即E W Dijkstra 狄克斯特拉 算法 现就介绍这种算法的思路和具体步骤 有关术语设在有向图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 min W 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 则v1 A中 其它顶点标出试探性标号为 参见表5 4 本节所列表中的k表示阶段 表5 4 1两点间的最短路问题 6 2 利用v1得到永久性标号 计算中各点新试探标号 l v2 min l v1 W12 l v2 min 0 5 5l v3 min l v1 W13 l v3 min 0 4 4同理得 l v4 7 l v5 l v6 l v7 取标号最小者为l v3 4 于是d v3 4 v3 A 见表5 5 表5 5 1两点间的最短路问题 7 3 v v3 用它计算中各点新试探标号 l v2 min l v3 W32 l v2 min 4 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步到达的两点最短路长矩阵必D A B 例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 每步从 E E T 中选取权最小的且与T不构成回路的边放入图T中 直到边数为n 1为止 破圈法 破回路法 以图G为基础i 在图G中 任取回路最长边 ii 去掉回路最长边 直至无回路 或剩下n 1条边 为止 则剩下的图形便是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 G Qk连通 则选择应满足下述条件 和关联 不是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 G F 确定最优解 调整F 使F的权和w F 最小 便可得出相应的最优欧拉图 最优解判别准则为 a F中无平行边 不考虑原边 b 若C为G中任一回路 且知C1 e e C 有相应添加边e F 则必使ii 举例阐明求解步骤 3邮路问题及旅行推销员问题 7 例5 9 求图5 25中所示的最短邮路 1 寻求初始可行解图5 25中 有四个奇度点v2 v4 v6 v8 可任意组成2对 任意图中 奇度点只能偶数个 例如 令v2和v4 v6和v8组成2对 然后任意给出相应的2条初等链v2v1v8v7v6v5v4和v6v5v4v3v2v1v8分别解决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回路 看是否存在带重复边之边权和大于其它边权和 例如检查回路v2v3v4v9v2 知故F中掉附加边 v2 v3 和 v3 v4 增加 v4 v9 和 v9 v2 得图5 28 进一步检查图5 28 发现回路中v1v2v9v6v7v8v1中 故又调整F 最后结果见图5 29 总附加边长度和变为15 3邮路问题及旅行推销员问题 11 2 旅行推销员问题的一般概念介绍 问题的提出旅行推销员离开原单位需遍访他所分配联系的每一座城市 然后返回 3邮路问题及旅行推销员问题 12 有关术语 对于图G V E i 至少包含图G中每个顶点一次的回路称推销员回路 求解出的最小长度回路称之为最优推销员回路 ii 恰恰包含图G中每个顶点一次的回路称之为哈密尔顿回路 而所求解出的最短哈密尔顿回路称为最优哈密尔顿回路 象网络图中可能不存在欧拉环游一样 网络图亦可能不存在哈密尔顿回路 但是要判断是否存在哈密尔顿回路比判断欧拉环游的存在要复杂的多 3邮路问题及旅行推销员问题 13 另外 如果邮路问题中的图G存在欧拉环游 则它必是最优的邮递路线 然而 一个图中的最优哈