运筹学最短路邮递员问题PPT课件.ppt

最短路问题最短路问题是最重要的优化问题之一 它不仅可以直接应用于解决生产实际的许多问题例如各种管道的铺设 线路的安排 厂区的布局 设备的更新等等 而且经常被作为一个基本工具 用于解决其它优化问题如运输网络的最小费用流等 最短距离 费时最少 费用最省 1 定义 权 赋权图 对图G的每一条边e 可赋与一个实数w e 称为边e的权 图G连同它边上的权称为赋权图 路中边权最小的称为最短路 权可以表示铁路长度 通讯网络的造价 网络中表示耗时等 2 狄克斯拉 Dijkstra 算法 最短路问题可以化为线性规划问题求解 也可以用动态规划方法求解 这里介绍一种有效算法 狄克斯拉 Dijkstra 算法 这一算法是1959年首次被提出来的 该算法适用于每条弧的权数 ij 0情形 算法的基本思路 从发点vs出发 有一个假想的流沿网络一切可能的方向等速前进 遇到新节点后 再继续沿一切可能的方向继续前进 则最先到达终点vt的流所走过的路径一定是最短的 为了实现这一想法 对假想流依次到达的点 依次给予p标号 表示vs到这些点的最短距离 对于假想流尚未到达的点给予T标号 表示vs到这些点的最短距离的估计值 具体作法如下 1 标p vs 0 其余点标T vi 2 由刚刚获得p标号的vi点出发 改善它的相邻点vj的T标号 即新的T vj min 老的T vj p vi ij 若T vj p vi ij 则记k vj vi 前点标记 3 找出具有最小T标号的点 将其标号改为p标号 若vt已获得p标号 则已找到最短路 由k vt 反向追踪 就可找出vs到vt的最短路径 p vt 就是vs到vt的最短距离 否则 转2 3 例求图中v1到v8的最短路 v4 v2 3 2 6 5 v3 v5 v6 v7 v8 6 3 5 5 2 1 1 1 4 7 9 解 标p v1 0 其余点标T vi i 2 3 4 5 6 7 8 T v2 min 0 3 3 k v2 v1T v3 min 0 5 5 k v3 v1T v4 min 0 6 6 k v2 v1将具有最小T标号的v2点的标号改为p标号 p v2 3 T v3 min 5 3 1 4 k v3 v2T v5 min 3 7 10 k v5 v2T v6 min 3 4 7 k v6 v2目前 点v3具有最小T标号 将其标号改为p标号 p v3 4 v1 4 v4 v2 3 2 6 5 v3 v5 v6 v7 v8 6 3 5 2 1 1 1 4 9 v1 7 p v1 0 p v2 3 p v3 4 T v4 min 6 4 1 5 k v4 v3T v6 min 7 4 2 6 k v6 v3 目前 点v4具有最小T标号 将其标号改为p标号 p v4 5 T v6 min 6 5 3 6 T v7 min 5 5 10 k v7 v4 目前 点v6具有最小T标号 将其标号改为p标号 p v6 6 T v5 min 10 6 2 8 k v5 v6T v7 min 10 6 1 7 k v7 v6T v8 min 6 9 15 k v8 v6 5 目前 点v7具有最小T标号 将其标号改为p标号 p v7 7 T v8 min 15 7 5 12 k v8 v7 p v5 8 T v8 min 12 8 6 12 p v8 12 反向追踪找最短路径 5 最短路径为 v1 v2 v3 v6 v7 v8 因p v8 12 所以v1 v8的最短距离为12 最短路问题不仅可以求解交通图中两点之间的最短距离 实际中很多问题也可变为最短路问题加以求解 例如设备更新问题 厂区合理布局问题等 兹举一例 例1 设备更新问题 某企业使用一台设备 在每年年底 企业都要决策下年度是购买一台新设备呢 还是继续使用这台设备 若购买新的 就要支付一笔购置费 如果使用旧设备 只要支付维修费 而维修费随着设备的使用年限延长而增加 现根据以往统计资料已经估算出设备在各年初的价格和不同使用年限的修理费用 分别如表1 表2所示 试确定一个五年内的设备更新计划 使五年内总支出最小 图上标示法下面我们结合例3介绍求解最短路问题的图上标示法 它比狄克斯拉算法更简洁 6 表1 表2 解 先根据表1 表2的数据画出设备更新费用网络图 如下图所示 图中点vi表示第i年开始 弧 vi vj 表示设备第i年初使用到第j年初 弧 vi vj 上的权数表示该期间设备所需的费用 这样 求五年内设备最优更新方案便转化为求v1 v6的最短路 v1 v2 v3 v4 v5 v6 16 16 17 17 18 22 30 41 59 22 30 41 23 31 23 7 设d vi 表示点vi到终点的最短距离 根据动态规划最优性原理 最短路径中任何子路径也必然是最短的 因此有d vi min ij d vj 注意 上式要对以vi为起点的所有弧 vi vj 进行计算 然后将计 j 算结果直接标在图中点vi的旁边 同时标出与点vi最近的邻接点 先从点v5算起 逆向进行 v1 v2 v3 v4 v5 v6 16 16 17 17 18 22 30 41 59 22 30 23 23 41 对于点v5 d v5 18 v5 v6 18v5 v6 对于点v4 d v4 min 17 18 23 23 v4 v6 23v4 v6 对于点v3 d v3 min 17 23 23 18 31 31 v3 v6 31 31v3 v6 对于点v2 d v2 min 16 31 22 23 30 18 41 41 v2 v6 41v2 v6 对于点v1 d v1 min 16 41 22 31 30 23 41 18 59 53 v1 v3 或v1 v4 53v1 v3 v6或v1 v4 v6 8 10 9 6 3 1 7 0 2 11 5 13 2 8 6 1 7 2 2 2 9 1 5 1 1 9 1 4 3 9 7 4 6 3 9 10 9 6 3 1 7 0 2 11 5 13 2 8 6 1 7 2 2 2 9 1 5 1 1 9 1 4 3 9 7 4 6 3 10 从一点到任意点的最短路 木器厂有六个车间 办事员经常要到各个车间了解生产进度 从办公室到各车间的路线由图1给出 找出点1 办公室 到其它各点 车间 的最短路 11 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 12 距离 价格 边eij或记为 vi vj 点 vi 权wij dij 13 表示网络图形的特点 1 与欧氏几何的区别为 图中线的长短并不能表示真实的长度 2 与地图的区别为两点之间的距离并不真实 14 表示网络图形的特点 网络 图论 中两点之间的距离由两点间的边上的权来表示 可由图中的点1 2与点1 3之间的关系来看 15 求网络上的一点到其它点的最短路 Dijkstra算法图示 16 Dinkstra标号法 这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法 在这个问题中我们讨论的是从网络中的点1到其它各点的最短路 17 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 18 0 从点1出发 因L11 0 在点1处标记 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 19 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 从已标号的点出发 找与这些相邻点最小权数 距离 者 找到之后 标号 边变红 20 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 2 21 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 从已标号的点出发 找与这些相邻点最小权数 距离 者 找到之后 标号 边变红 2 22 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 从已标号的点出发 找与这些相邻点最小权数 距离 者 找到之后 标号 边变红 2 3 23 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 重复上述步骤 直至全部的点都标完 2 3 24 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 重复上述步骤 直至全部的点都标完 2 3 4 25 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 重复上述步骤 直至全部的点都标完 2 3 4 26 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 重复上述步骤 直至全部的点都标完 2 3 4 7 27 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 2 3 4 7 28 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 2 3 4 7 8 29 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 2 3 4 7 8 30 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 2 3 4 7 8 13 31 5 1 2 7 5 6 3 4 2 5 5 2 7 3 1 3 5 7 1 0 2 3 4 7 8 13 32 小结 从点1出发 因L 1 1 0 在点1处标记 从点1出发 找相邻点r使得边L 1 r 权数 距离 最小 若L 1 r L 1 1 d 1 r 将标于点r处 并将边1r变红 0 L 1 r 33 从已标号的点出发 找与这些相邻点最小权数 距离 者 若L 1 p Min L 1 r d r p 这里r为已标号者下标 p为未标号下标 则将标于p处 并把 r p 边变红 重复上述步骤 直至全部的点都标完 L 1 p 34 对有向图同样可以用标号算法 例如图 有一批货物要从v1运到v9 弧旁数字表示该段路长 求最短运输路线 35 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 36 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 37 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 38 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 39 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 40 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 5 41 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 5 42 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 6 6 5 43 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 6 6 5 44 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 6 7 5 6 45 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 6 7 5 6 8 5 46 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 6 7 5 6 8 5 9 47 v1 v9 v8 v7 v6 v5 v4 v3 v2 3 3 3 3 3 4 2 5 5 2 2 2 1 4 0 3 4 6 7 5 6 8 5 9 48 最短路的矩阵算法首先写出弧长矩阵D第一步 划去矩阵D中第一列 并给第一行以标号0 49 第二步 在已标号中未划去的元素中 寻找出最小的元素aij并圈起来 此时把第j列划去 同时给第j行标号i 并把第j行中未划去的各元素都加上aij 第三步 如果各行均已获得标号 则停止 并利用标号倒向追踪 得到v1到各点的最短路 若存在未标号行 返回第二步 50 例求v1到各点vj的最短路 v1 v4 v2 v5 v3 v6 1 2 5 3 2 4 2 3 2 4 4 1 2 51 v1v2v3v4v5v6v101 2 v2 034 v3 2051 v4 4 04 v5 230 v6 2 20 52 v1v2v3v4v5v6001 2 v2 034 v3 2051 v4 4 04 v5 230 v6 2 20 53 v1v2v3v4v5v6001 2 v2 034 v3 2051 v4 4 04 v5 230 v6 2 20 54 v1v2v3v4v5v6001 2 v2 034 v3 2051 v4 4 04 v5 230 v6 2 20 55 v1v2v3v4v5v6001 2 1 03 14 1 v3 2051 v4 4 04 v5 230 v6 2 20 56 v1v2v3v4v5v6001 2 1 045 v3 2051 v4 4 04 v5 230 v6 2 20 57 v1v2v3v4v5v6001 2 1 045 v3 2051 v4 4 04 v5 230 v6 2 20 58 v1v2v3v4v5v6001 2 1 045 v3 2051 1 4 04 v5 230 v6 2 20 59 v1v2v3v4v5v6001 2 1 045 v3 2051 1 4 04 2 v5 230 v6 2 20 60 2020 3 19 61 v1v2v3v4v5v6001 2 1 045 v3 2051 1 4 06 v5 230 v6 2 20 62 v1v2v3v4v5v6001 2 1 045 v3 2051 1 4 06 v5 230 v6 2 20 63 v1v2v3v4v5v6001 2 1 045 2 2051 1 4 06 v5 230 v6 2 20 64 v1v2v3v4v5v6001 2 1 045 2 2051 4 1 4 06 v5 230 v6 2 20 65 v1v2v3v4v5v6001 2 1 045 2 2055 1 4 06 v5 230 v6 2 20 66 v1v2v3v4v5v6001 2 1 045 2 2055 1 4 06 3 230 v6 2 20 67 v1v2v3v4v5v6001 2 1 045 2 2055 1 4 06 3 230 v6 2 20 68 v1v2v3v4v5v6001 2 1 045 2 2055 1 4 06 3 230 5 2 20 69 v1v2v3v4v5v6001 2 1 045 2 2055 1 4 06 3 230 6 2 2 70 v1到各点vj的最短路 v1 v4 v2 v5 v3 v6 1 3 1 2 71 72 73 例2教育部门打算在某新建城区建一所学校 让附近七个居民区的学生就近入学 七个居民区之间的道路如下图所示 学校应建在哪个居民区 才能使大家都方便 图中距离单位 百米 74 75 76 77 78 79 80 例 已知一个地区的交通网络如下 其中点代表居民小区 边表示公路 lij为公路距离 问区中心医院应建在小区居民就诊时所走路程最短 81 v1 v2 v3 v4 v5 v6 v7 60 18 25 20 15 15 30 20 30 82 解 这是一个选择地址问题 实际要求出图的中心 可化成一系列求最短路问题 先求出v1到其他各点的最短路长dj 令d v1 max d1 d2 d7 表示若医院建在v1 则离医院最远的小区距离为d v1 依次计算v2 v3 v7到其余各点的最短路 类似求出d v2 d v3 d v7 d vi 中 I 1 2 7 中最小者 83 84 由于d v6 48最小 所以医院应建在v6 此时离医院最远小区距离为48 比医院建在其他小区时距离都短 85 中国邮递员问题一 一笔画问题定义 欧拉链 给定一个多重连通图G 若存在一条链 通过每边一次且仅一次 则称为这个链为欧拉链 86 定义 欧拉圈 给定一个多重连通图G 若存在一条圈 通过每边一次且仅一次 则称为这个圈为欧拉圈 定义 欧拉图 含有一条欧拉圈的图 称为欧拉图 87 定理多重连通图G是欧拉图 当且仅当G中无奇顶点 推论多重连通图G有欧拉链的充分必要条件是G恰有两个奇顶点 88 v1 v4 v3 v2 顶点的度d v1 4 d v2 2 d v3 4 d v4 2全为偶数 89 v1 v4 v3 v2 是欧拉图 存在欧拉圈 可从任一点出发 90 v1 v4 v3 v2 91 v1 v4 v3 v2 92 v1 v4 v3 v2 93 v1 v4 v3 v2 94 v1 v4 v3 v2 95 v1 v4 v3 v2 顶点的度d v1 3 d v2 2 d v3 3 d v4 2两个奇顶点 96 v1 v4 v3 v2 存在欧拉链 且从其中一个奇顶点开始 结束在另一个奇顶点 97 v1 v4 v3 v2 98 v1 v4 v3 v2 99 v1 v4 v3 v2 100 v1 v4 v3 v2 存在欧拉链 且从其中一个奇顶点开始 结束在另一个奇顶点 101 中国邮递员问题 一个邮递员送信 要走完他负责投递的全部街道 完成任务后回到邮局 应如何选择行走路线 才能使所走的路线最短 如果街区图中没有奇顶点 则是一个欧拉图 如果有奇顶点 则某些边必定重复走一次或多次 我们要求重复走过边的总长最小 102 奇偶点作业法步骤 1确定第一个可行方案 找到图中所有奇顶点 必有偶数个点 将它们两两配对 新图中无奇顶点 得到第一个可行方案 2调整可行方案 使重复边总长度下降 103 3检查图中的每个圈 如果每个圈重复边总长度不超过该圈总长度的一半 则已求得最优解 否则进行调整 将这个圈的重复边去了 而将原来没有重复边的各边加上重复边 其他各圈的边不变 根据2再一次调整 104 例设有街道图 各边均标出了街道的长 权 假定邮递员从v1点出发 求他的最优投递路线 105 v9 v1 v8 v7 v6 v5 v4 v3 v2 4 3 4 3 4 4 4 9 6 5 5 2 106 v9 v1 v8 v7 v6 v5 v4 v3 v2 4 3 4 3 4 4 4 9 6 5 5 2 有四个奇顶点 107 v9 v1 v8