中国邮递员问题.ppt

运筹学之中国邮递员问题 昆明理工大学信息工程与自动化学院 七桥问题SevenBridgesProblem 引点 18世纪著名古典数学问题之一 在哥尼斯堡的一个公园里 有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来 问是否可能从这四块陆地中任一块出发 恰好通过每座桥一次 再回到起点 图见P251页 图10 1 从七桥问题到一笔画思想 欧拉于1736年研究并解决了此问题 他用点表示岛和陆地 两点之间的连线表示连接它们的桥 将河流 小岛和桥简化为一个网络 把七桥问题化成判断连通网络能否一笔画的问题 之后他发表一篇论文 证明了上述走法是不可能的 并且给出了连通网络可一笔画的充要条件这一著名的结论 如图可见P251页图10 1 b C D A B 因为图中的每个点都只与奇数条相关联 所以不可能一笔画出 一笔画问题 什么是一笔画问题呢 一笔画问题 从某一点开始画画 笔不离纸 各条线路仅画一次 最后回到原来的出发点 想一想 图1和图2当中哪一个图满足 从图中任何一点出发 途径每条边 最终还能回到出发点 由此试想一下 一个图应该满足什么条件才能达到上面要求呢 一笔画问题 中国邮路问题基础 凡是能一笔画出的图 奇点的个数最多有两个 始点与终点重合的一笔画问题 奇点的个数必是0 在一个多重边的连通图中 从某个顶点出发 经过不同的线路 又回到原出发点 这样的线路必是欧拉图 即能一笔画出的图必是欧拉图 定理1 连通的多重图G是欧拉图 当且仅当G中无奇点 定理2 任何一个图中的奇点个数必为偶数 推论 连通的多重图有欧拉链 当且仅当图中有两个奇点 什么是欧拉链 给定一个连通多重图G 若存在一条链 过每边一次 则称这条链为欧拉链 那什么又事欧拉圈呢 若存在一个简单圈 过每边一次 且仅一次 则称为欧拉圈 一个图若有欧拉圈就可以称之为欧拉图 中国邮递员问题 一个邮递员送信 要走完他负责投递的全部街道 投完后回到邮局 应该怎样走 使所走的路程最短 这个问题是我国管梅谷同志1962年首先求出来的 因此在国际上通称为中国邮递员问题 在物流活动中 经常会遇到这样的问题 如 每天在大街小巷行驶的垃圾车 洒水车 各售货点的送货车等都需要解决一个行走的最短路程问题 这个问题就是一笔画问题 定理 连通多重图G有欧拉圈 当且仅当G中无基点 推论 连通多重图G有欧拉链 当且仅当G恰有两个基点 如图P277图10 30所示 现在的问题是 如果我们已经知道图G是可以一笔画的 首先引入割边概念 设e是连通图G的一个边 如果从G中丢去e 图就不连通了 则称e是图G的割边 奇偶点图上作业法 如果在邮递员所负责的范围内 街道图中没有奇点 那他就可以从邮局出发 走过每街道一次 且仅一次 最后回到邮局 这样他走的路程 然而对奇点的街道图 就必须在某些街道上重复走一次或多次 ppt17页 例见P278图10 31 a b 解决这样的问题 可以采用奇偶点图上作业法 如果在配送范围内 街道中没有奇点 那么他就可以从配送中心出发 走过每条街道一次 且仅一次 最后回到配送中心 这样他所走的路程也就是最短的路程 对于有奇点的街道图 该怎么办呢 这时就必须在每条街道上重复走一次或多次 举例说明 如图所示 1 1 1 1 1 1 1 1 1 V1 V2 V4 V3 V2 V4 V6 V5 V4 V6 V5 V3 V1总权为12另一路径见书P278路径 b 总权为11 如果在某条路线中 边 vi vj 上重复走几次 我们就在图中vi vj之间增加几条边 令每条边的权和原来的权相等 并把所增加的边 称为重复边 于是这条路线就是相应的新图中的欧拉图 原来的问题可以叙述为在一个有奇点的图中 要求增加一些重复边 使新图不含奇点 并且重复边的总权为最小 我们把使新图不含奇点而增加的重复边简称为可行 重复边 方案 使总权最小的可行方案为最优方案 中国邮递员问题的实质 中国邮递员问题 可以叙述为在一个有奇点的图中 要求增加一些重复边 使新图不含奇点 并且重复边的总权为最小 现在的问题是第一个可行方案如何确定 在确定一个可行方案后 怎么判断这个方案是否为最优方案 若不是最优方案 如何调整这个方案 车辆从某配送中心 v1 出发 给街道边上的超市 v2 v3 v4 v5 v6 v7 v8 v9 送货 如图所示 习题 显然街区图上有奇点 4个分别为V2 V4 V6 V6 不满足 一笔画 的条件 则必然有一些街道要被重复走过 添加重复边 才能回到原出发点 此时得到的图就无奇点 那么该怎样添加重复边 使得图中全为偶点呢 其实可以通过连接匹配的奇点得到 第一步 确定初始可行方案 这样就得到初始方案 在这个图中 没有奇点 故称它为欧拉图 对应于这个可行方案 重复边总权为51 2W12 W23 W34 2W45 2W56 W67 W78 2W18 51 问题 这样的可行方案是不是只有一种呢 在确定一个可行方案后 怎么判断这个方案是否为最优方案 若不是最优方案 如何调整这个方案 第二步 调整可行方案使重复边总权下降 最优方案必须满足以下 1 2 两个条件 1 在最优方案中 图的每一边最多有一条重复边 2 在最优方案中 图中每个圈上的重复边的总权不大于该圈总权的一半 为什么 第二步 调整可行方案 首先 去掉多余的重复边 使图中每一边最多有一条重复边 见图3 图3 第二步 调整可行方案 其次 如果把图中某个圈上的重复边去掉 而给原来没有重复边的边上加上重复边 图中仍然没有奇点 因而如果在某个圈上重复边的总权数大于这个圈的总权数的一半 像上面所说的那样做一次调整 将会得到一个总权下降的可行方案 第二步 调整可行方案 在书P280图10 34中 圈 v2 v3 v4 v9 v2 的总长度为24 但圈上重复边总权为14 大于该圈总长度的一半 因此可以做一次调整 以 v2 v9 v9 v4 上的重复边代 v2 v3 v3 v4 上的重复边 使重复边总长度下降为17 见图4 图4 检查P280图10 35中圈 v1 v2 v9 v6 v7 v8 v1 的总长度为24 但圈上重复边总权为13 大于该圈总长度的一半 因此可以做一次调整 使重复边总长度下降为15 见图5 图5 检查图5 均满足条件 1 和 2 于是得到最优方案 图5中的任一欧拉圈都是汽车的最优配送路线 如 v1 v2 v9 v8 v1 v8 v7 v6 v5 v4 v9 v6