中国邮递员问题

演示文稿中国邮递员问题目前一页\总数三十七页\编于二十一点（优选）中国邮递员问题目前二页\总数三十七页\编于二十一点主要内容七桥问题与一笔画中国邮递员问题欧拉图及求欧拉回路的算法求解中国邮递员问题的算法目前三页\总数三十七页\编于二十一点七桥问题SevenBridgesProblem18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？目前四页\总数三十七页\编于二十一点欧拉于1736年研究并解决了此问题，

他用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。之后他发表一篇论文，证明了上述走法是不可能的。并且给出了连通网络可一笔画的充要条件这一著名的结论。目前五页\总数三十七页\编于二十一点一笔画问题一笔画问题：从某一点开始画画，笔不离纸，各条线路仅画一次，最后回到原来的出发点。目前六页\总数三十七页\编于二十一点bca图1v2v3v1v4图2图1和图2当中哪一个图满足：从图中任何一点出发，途径每条边，最终还能回到出发点？试想：一个图应该满足什么条件才能达到上面要求呢？目前七页\总数三十七页\编于二十一点一笔画问题凡是能一笔画出的图，奇点的个数最多有两个。始点与终点重合的一笔画问题，奇点的个数必是0。奇点：那个点的角度来看，数有多少条线从连接着那个点，如果连接那个点的线的数量是奇数条，那这个点就是奇点，反之，就是偶点。在一个多重边的连通图中，从某个顶点出发，经过不同的线路，又回到原出发点，这样的线路必是尤拉图，即能一笔画出的图必是尤拉图。目前八页\总数三十七页\编于二十一点定理：连通的多重图G是尤拉图，当且仅当G中无奇点。定理：任何一个图中的奇点个数必为偶数。推论：连通的多重图有尤拉链，当且仅当图中有两个奇点。目前九页\总数三十七页\编于二十一点欧拉图及求欧拉回路的算法欧拉行迹—含所有边恰好一次的行迹欧拉回路—含所有边恰好一次的回路欧拉图—存在欧拉回路的图

设G是连通图,下列命题等价:(1)G是欧拉图.(2)每个顶点的度数都是偶数.(3)G是两两无公共边的圈的并.目前十页\总数三十七页\编于二十一点欧拉图及求欧拉回路的算法求欧拉回路的算法(Fleury算法，1921年)算法思想:“过河拆桥,尽量不走独木桥”.

即若已选定迹,从中选取下一条边使得与相关联,且不是的桥,除非无边可选.Fleury算法的复杂度是目前十一页\总数三十七页\编于二十一点欧拉图及求欧拉回路的算法求欧拉回路的算法(回路算法)算法思想:首先得到一个回路C1,再在剩下的图G-C1中求一条与C1有公共顶点的回路C2,则C1与

C2构成一个更长的回路,继续下去可得到含所有边恰好一次的回路.回路算法的复杂度是上述两算法都是在连通欧拉图中求欧拉回路的算法.目前十二页\总数三十七页\编于二十一点中国邮递员问题一个邮递员送信，要走完他负责投递的全部街道，投完后回到邮局，应该怎样走，使所走的路程最短？这个问题是我国管梅谷同志1960年首先求出来的，因此在国际上通称为中国邮递员问题。在物流活动中，经常会遇到这样的问题，如：每天在大街小巷行驶的垃圾车、洒水车、各售货点的送货车等都需要解决一个行走的最短路程问题。这个问题就是一笔画问题。目前十三页\总数三十七页\编于二十一点管梅谷管梅谷教授。上海市人。1957年毕业于华东师范大学数学系。历任山东师范大学讲师、副教授、教授、校长，中国运筹学会第一、二届常务理事，山东省数学学会第四届副理事长，山东省运筹学会第一届副理事长，山东省世界语协会理事长。是第六届全国政协委员。从事运筹学及其应用的研究，对最短投递路线问题的研究取得成果。所提模型在国外称为中国投递问题。目前十四页\总数三十七页\编于二十一点中国邮递员问题在一个连通的赋权图G（V，E）中，求一条回路，使该回路包含G中的每条边至少一次，且该回路的权最小．（称此回路为最优回路或者中国邮路）目前十五页\总数三十七页\编于二十一点求解中国邮递员问题的算法

如果中国邮递员问题中的图是欧拉图，那么欧拉回路就是最优回路。一般情形下（不是欧拉图），最优回路包含某些边至少两次。这时求最优回路的思想是：在图G中添加一些重复边使新图G*成为欧拉图，且使得所有添加的重复边的权和最小。再由G*的欧拉回路得到G的最优回路。目前十六页\总数三十七页\编于二十一点求解中国邮递员问题的算法管梅谷教授首先提出的方法是奇偶点图上作业法（1962年）Edmonds，Johnson（1973年）给出有效算法。复杂度为目前十七页\总数三十七页\编于二十一点求解中国邮递员问题的算法（例）目前十八页\总数三十七页\编于二十一点求解中国邮递员问题的算法（例）目前十九页\总数三十七页\编于二十一点解决这样的问题，可以采用奇偶点图上作业法：如果在配送范围内，街道中没有奇点，那么他就可以从配送中心出发，走过每条街道一次，且仅一次，最后回到配送中心，这样他所走的路程也就是最短的路程。目前二十页\总数三十七页\编于二十一点问题对于有奇点的街道图，该怎么办呢？这时就必须在每条街道上重复走一次或多次。目前二十一页\总数三十七页\编于二十一点举例说明如图所示。v1v2v3v4v5v6324452648目前二十二页\总数三十七页\编于二十一点如果在某条路线中，边[vi,vj]上重复走几次，我们就在图中vi,vj之间增加几条边，令每条边的权和原来的权相等，并把所增加的边，称为重复边，于是这条路线就是相应的新图中的尤拉图。原来的问题可以叙述为在一个有奇点的图中，要求增加一些重复边，使新图不含奇点，并且重复边的总权为最小。我们把使新图不含奇点而增加的重复边简称为可行（重复边）方案，使总权最小的可行方案为最优方案。目前二十三页\总数三十七页\编于二十一点现在的问题是第一个可行方案如何确定？在确定一个可行方案后，怎么判断这个方案是否为最优方案？若不是最优方案，如何调整这个方案？目前二十四页\总数三十七页\编于二十一点车辆从某配送中心（v1）出发，给街道边上的超市（v2,v3,v4,v5,v6,v7,v8,v9）送货，如图1所示。举个例子v1v3v2v4v8v7v6v5v9254339546444图1目前二十五页\总数三十七页\编于二十一点显然街区图上有奇点（4个），不满足“一笔画”的条件，则必然有一些街道要被重复走过（添加重复边）才能回到原出发点。此时得到的图就无奇点。那么该怎样添加重复边，使得图中全为偶点呢？其实可以通过连接匹配的奇点得到！目前二十六页\总数三十七页\编于二十一点第一步：确定初始可行方案v1v3v2v4v8v7v6v5v9254339546444图2目前二十七页\总数三十七页\编于二十一点这样就得到初始方案.在这个图中，没有奇点，故称它为欧拉图。对应于这个可行方案，重复边总权为51。目前二十八页\总数三十七页\编于二十一点思考这样的可行方案是不是只有一种呢？在确定一个可行方案后，怎么判断这个方案是否为最优方案？若不是最优方案，如何调整这个方案？目前二十九页\总数三十七页\编于二十一点第二步：调整可行方案最优方案必须满足以下（1）（2）两个条件：（1）在最优方案中,图的每一边最多有一条重复边（2）在最优方案中,图中每个圈上的重复边的总权不大于该圈总权的一半。目前三十页\总数三十七页\编于二十一点第二步：调整可行方案首先，去掉多余的重复边，使图中每一边最多有一条重复边。见图3v1v2v3v4v5v6v7v8v9444342346955图3目前三十一页\总数三十七页\编于二十一点第二步：调整可行方案其次，如果把图中某个圈上的重复边去掉，而给原来没有重复边的边上加上重复边，图中仍然没有奇点。因而如果在某个圈上重复边的总权数大于这个圈的总权数的一半，像上面所说的那样做一次调整，将会得到一个总权下降的可行方案。目前三十二页\总数三十七页\编于二十一点第二步：调整可行方案在图4中，圈（v2,v3,v4,v9,v2）的总长度为24，但圈上重复边总权为14，大于该圈总长度的一半，因此可以做一次调整，以[v2,v9]，[v9,v4]上的重复边代[v2,v3]，[v3,v4]上的重复边，使重复边总长度下降为17。见图4目前三十三页\总数三十七页\编于二十一点v1v2v3v4v5v6v7v8v9444342346955图4目前三十四页\总数三十七页\编于二十一点检查图4中圈（v1,v2,v9,v6,v7,v8,v1）的总长度为24，但圈上重复边总权为13，大于该圈总长度的一半，因此可以做一次调整，使