中国邮递员问题(1)ppt课件

1、运筹学之 中国邮递员问题昆明理工大学昆明理工大学信息工程与自动化学院信息工程与自动化学院 七桥问题七桥问题 Seven Bridges Problem引点引点n18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸衔接起来。问能否能够从这四块陆地中任一块出发，恰好经过每座桥一次，再回到起点？n (图见P251页，图10-1)从七桥问题到一笔画思想从七桥问题到一笔画思想n欧拉于1736年研讨并处理了此问题， 他用点表示岛和陆地，两点之间的连线表示衔接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判别连通网络能否一笔画的问题。之后他发表一篇论文，证

2、明了上述走法是不能够的。并且给出了连通网络可一笔画的充要条件这一著名的结论。如图可见如图可见P251页图页图10-1bCDAB由于图中的每个点都只与奇数条相关联，所以不能够一笔画出由于图中的每个点都只与奇数条相关联，所以不能够一笔画出一笔画问题一笔画问题n什么是一笔画问题呢？n一笔画问题：从某一点开场画画，笔不离纸，各条线路仅画一次，最后回到原来的出发点。想一想：想一想：bca图图1v2v3v1v4图图2 图图1和图和图2当中哪一个图满足：从图中任何一点出发，当中哪一个图满足：从图中任何一点出发，途径每条边，最终还能回到出发点？途径每条边，最终还能回到出发点？ 由此试想一下：一个图应该满足什么

3、条件才干到达由此试想一下：一个图应该满足什么条件才干到达上面要求呢？上面要求呢？一笔画问题中国邮路问题根底一笔画问题中国邮路问题根底n凡是能一笔画出的图，奇点的个数最多有两个。始点与终点重合的一笔画问题，奇点的个数必是0。n在一个多重边的连通图中，从某个顶点出发，经过不同的线路，又回到原出发点，这样的线路必是欧拉图，即能一笔画出的图必是欧拉图。n定理1：连通的多重图G是欧拉图，当且仅当G中无奇点。n定理2 ：任何一个图中的奇点个数必为偶数。n推论：连通的多重图有欧拉链，当且仅当图中有两个奇点。n什么是欧拉链?n给定一个连通多重图G，假设存在一条链，过每边一次，那么称这条链为欧拉链。n那什么又事

4、欧拉圈呢 ？n假设存在一个简单圈，过每边一次，且仅一次，那么称为欧拉圈。n一个图假设有欧拉圈就可以称之为欧拉图中国邮递员问题中国邮递员问题 n一个邮递员送信，要走完他担任投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最短？ n这个问题是我国管梅谷同志1962年首先求出来的，因此在国际上通称为中国邮递员问题。在物流活动中，经常会遇到这样的问题，如：每天在大街小巷行驶的渣滓车、洒水车、各售货点的送货车等都需求处理一个行走的最短路程问题。 n这个问题就是一笔画问题。n定理：连通多重图G有欧拉圈，当且仅当G中无基点。n推论：连通多重图G有欧拉链，当且仅当G恰有两个基点。n如图P277 图10

5、-30 所示 ，如今的问题是：n假设我们曾经知道图G是可以一笔画的，n首先引入割边概念，设e是连通图G的一个边，假设从G中丢去e，图就不连通了，那么称e是图G的割边。奇偶点图上作业法奇偶点图上作业法n假设在邮递员所担任的范围内，街道图中没有奇点，那他就可以从邮局出发，走过每街道一次，且仅一次，最后回到邮局，这样他走的路程。n然而对奇点的街道图，就必需在某些街道上反复走一次或多次。ppt17页n例见P278 图10-31 a、bn处理这样的问题，可以采用奇偶点图上作业法：假设在配送范围内，街道中没有奇点，那么他就可以从配送中心出发，走过每条街道一次，且仅一次，最后回到配送中心，这样他所走的路程也

6、就是最短的路程。n对于有奇点的街道图，该怎样办呢？n这时就必需在每条街道上反复走一次或多次。举例阐明举例阐明n如下图。v1v2v3v4v5v6324452648111111111V1V2V4V3V2V4V6V5V4V6V5V3V1 总权为总权为 12 另一途径见书另一途径见书P278 途径途径b总权为总权为11.n假设在某条道路中，边vi,vj上反复走几次，我们就在图中vi,vj之间添加几条边，令每条边的权和原来的权相等，并把所添加的边，称为反复边，于是这条道路就是相应的新图中的欧拉图。n原来的问题可以表达为在一个有奇点的图中，要求添加一些反复边，使新图不含奇点，并且反复边的总权为最小。n我们

7、把使新图不含奇点而添加的反复边简称为可行反复边方案，使总权最小的可行方案为最优方案。中国邮递员问题的本质中国邮递员问题的本质n中国邮递员问题可以表达为在一个有奇点的图中，要求添加一些反复边，使新图不含奇点，并且反复边的总权为最小。n如今的问题是第一个可行方案如何确定？n在确定一个可行方案后，怎样判别这个方案能否为最优方案？n假设不是最优方案，如何调整这个方案？n车辆从某配送中心v1出发，给街道边上的超市v2,v3,v4,v5,v6,v7,v8,v9送货，如下图。习题习题v1v3v2v4v8v7v6v5v9254339546444图图1n显然街区图上有奇点4个分别为V2，V4，V6，V6，不满足

8、“一笔画的条件，那么必然有一些街道要被反复走过添加反复边才干回到原出发点。此时得到的图就无奇点。n那么该怎样添加反复边，使得图中全为偶点呢？n其实可以经过衔接匹配的奇点得到！第一步：确定初始可行方案第一步：确定初始可行方案v1v3v2v4v8v7v6v5v9254339546444图图2n这样就得到初始方案.在这个图中，没有奇点，故称它为欧拉图。对应于这个可行方案，反复边总权为51。n2W12+W23+W34+2W45+n 2W56+W67+W78+2W18=51问题：问题：n这样的可行方案是不是只需一种呢？n在确定一个可行方案后，怎样判别这个方案能否为最优方案？n假设不是最优方案，如何调整这

9、个方案？第二步：调整可行方案使反复边总权下降第二步：调整可行方案使反复边总权下降 n最优方案必需满足以下12两个条件：n1在最优方案中,图的每一边最多有一条反复边n2在最优方案中,图中每个圈上的反复边的总权不大于该圈总权的一半。 为什么?第二步：调整可行方案第二步：调整可行方案n首先，去掉多余的反复边，使图中每一边最多有一条反复边。见图3v1v2v3v4v5v6v7v8v9444342346955图图3第二步：调整可行方案第二步：调整可行方案n其次，假设把图中某个圈上的反复边去掉，而给原来没有反复边的边上加上反复边，图中依然没有奇点。因此假设在某个圈上反复边的总权数大于这个圈的总权数的一半，像

10、上面所说的那样做一次调整，将会得到一个总权下降的可行方案。第二步：调整可行方案第二步：调整可行方案n在书P280图10-34中，n 圈v2,v3,v4,v9,v2的总长度为24，但圈上反复边总权为14，大于该圈总长度的一半，因此可以做一次调整，以v2,v9，v9,v4上的反复边代v2,v3，v3,v4上的反复边，使反复边总长度下降为17。见图4v1v2v3v4v5v6v7v8v9444342346955图图4n检查P280图10-35中圈v1,v2, v9, v6,v7, v8,v1的总长度为24，但圈上反复边总权为13，大于该圈总长度的一半，因此可以做一次调整，使反复边总长度下降为15。见图5。图图5n检查图5，均满足条件1和2，于是得到最优方案。图5中的任一欧拉圈都是汽车的最优配送道路。n如：v1-v2-v9-v8-v1-v8-v7-v6-v5-v4-v