毕业论文-中国邮递员问题综述

本科毕业论文(设计)题目：中国邮递员问题综述学院统计与数理学院专业信息与计算科学班级2007级1班学号20070534119姓名高坤指导教师王继强山东财政学院教务处制二O一一年五月统计与数理学院本科毕业论文设计1中国邮递员问题综述高坤摘要：本文综合论述了运筹学中的中国邮递员问题，首先简介了该问题的起源，然后建立起该问题的图论模型，旨在使邮递员的投递线路最短，给出了算法和步骤，再借助lingo软件进行了实证分析.中国邮递员问题的研究在网上交易和电子商务快速发展的今天尤其具有重要的现实意义.关键词：投递一笔画欧拉回路最短路Lingo一、引言图论是应用十分广泛的运筹学分支，它已广泛的应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域.在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决.例如，在组织生产中，为完成某项任务，各工学之间怎么样衔接，才能使生产任务完成的又快又好.一个邮递员送信，要走完他负责投递的所有街道，完成任务后回到邮局，应该按照怎么样的路线走，才能使得走的路线最短.中国投递员问题是1960年我们从生产实际中提出的一个数学问题，它是从下述实际问题中抽象出来的：“一个投递员应该怎么选择一条线路，才能既把所有由他负责的信件都送到，而所走的路程又最短”.在我们开始研究中国投递员问题以前，国外有人研究过所谓旅行售货员的问题，即：“一个售货员要到n个城市去售货，问他应该选择怎样的一条线路，才能既走遍所有城市，并且走的路程最短”.这是一个著名的难题.当n较大时，即使使用大型电子计算机，也很难解决.投递员面临的问题显然可以归纳为旅行售货员问题，事实上，只要把投递员必须送的每一个地点看成是一个城市就行了.但是一般来说，投递员每次要到约二、三百个地点送信，如果归纳为旅行售货员问题来解决，将是一个规模很大的问题，是无法解决的.但是，在仔细分析了投递员面临的问题后，我们发现这个问题具有一定的特点，即需要送信的地点一般都是比较密集的排列在街道上的，因此，实际上，我们称这个问题为“最短投递线路问题”，1965年后国外称之为“中国投递员问题”.二、概念与原理一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图),(EVG中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小．也就是说要从包含G的每条边的回路中找一条统计与数理学院本科毕业论文设计2权数最小的回路．在实际生活中，人们为了反映一些对象之间的关系，常常会在纸上用点和线画出各种各样的示意图.例如：8世纪时，欧洲有一个风景秀丽的小城哥尼斯堡,那里有七座桥.如图1所示：河中的小岛A与河的左岸B、右岸C各有两座桥相连结，河中两支流间的陆地D与A、B、C各有一座桥相连结.问：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？这个例子是历史上非常有名的哥尼斯堡7桥问题.哥尼斯堡现在是立陶宛共和国的一个城市，图1是当地奈发夫岛附近的地域图，此例子就是当地人民中间流传久远的一个难题.直到1736年，数学家欧拉首次系统研究并完全解决了这类问题.图1七桥问题引起了著名数学家欧拉（1707—1783）的关注.他把具体七桥布局化归为图2所示的简单图形，于是，七桥问题就变成一个一笔划问题：怎样才能从A、B、C、D中的某一点出发，一笔划出这个简单图形（即笔不离开纸，而且a、b、c、d、e、f、g各条线只画一次不准重复），并且最后返回起点？ABCDabcdfgde图2统计与数理学院本科毕业论文设计3一笔划出的图形中的各点或者都是与偶数条线相连的点，或者其中只有两个点与奇数条线相连.欧拉定理:如果一个网络是连通的并且奇顶点的个数等于0或2，那么它可以一笔划出，否则它不可以一笔划出.定义经过G的每条边的迹叫做G的Euler迹；闭的Euler迹叫做Euler回路或E回路,含Euler回路的图叫做Euler图.直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点.定理1（1）G是Euler图的充分必要条件是G连通且每顶点皆偶次.（2）G是Euler图的充分必要条件是G连通且diiCG1，iC是圈，)()()(jiCECEji.（3）G中有Euler迹的充要条件是G连通且至多有两个奇次点.另外一种表述：定理2对连通图G（V，E），下列条件是相互等价的：（1）G是一个欧拉图；（2）G的每一个节点的度数都是偶数；（3）G的边集合E可以分解为若干个回路的并．如果一幅图是由点和线连接组成，那么与奇数条线相连的点叫“奇点”，与偶数条线相连的点叫“偶点”．三、运作模式一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题．用图论的述语，在一个连通的赋权图),(EVG中，要寻找一条回路，使该回路包含G中的每条边至少一次，且该回路的权数最小．也就是说要从包含G的每条边的回路中找一条权数最小的回路．统计与数理学院本科毕业论文设计4如果G是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本次的要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．所谓欧拉G路与哥尼斯堡7桥问题相联系的．在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点．与此相反，设),(EVG为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉回路，并称图G为欧拉图．在一个图中，连接一个节点的边数称为该节点的度数．对欧拉图，我们有下列结果：定理3下列条件是相互等价的：（1）G是一个欧拉图；（2）G的每一个节点的度数都是偶数；（3）G的边集合E可以分解为若干个回路的并．证明：()()12已知G为欧拉图，则必存在一个欧拉回路．回路中的节点都是偶度数．()()23设G中每一个节点的度数均为偶数．若能找到一个回路1C使1CG，则结论成立．否则，令11\CGG，由1C上每个节点的度数均为偶数，则1G中的每个节点的度数亦均为偶数．于是在1G必存在另一个回路2C．令2121\CGGG，···．由于G为有限图，上述过程经过有限步，最后必得一个回路rC使rrrCGG\1上各节点的度数均为零，即1rrGC这样就得到G的一个分解rCCCG21．()()31设GCCCr12，其中iC（I=1,2,…,r）均为回路．由于G为连通图，对任意回路iC,必存在另一个回路jC与之相连，即iC与jC存在共同的节点．现在我们从图G的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，···，这样一直走下去就可走遍G的每条边且只走过一次,最后回到原出发节点，即G为一个欧拉图．利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了．下面介绍一种求欧拉回路的算法即：弗罗莱算法算法步骤如下：（1）任取起始点vvR00,;（2）设路)},({,),,({),,({1211201rriiriiivvevvevveR已选出，则从E\},,,{21reee中选出统计与数理学院本科毕业论文设计5边1re，使1re与riv相连，除非没有其它选择，Gerr\{}1仍应为连通的．（3）重复步骤（2），直至不能进行下去为止．定理4有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数）相等．如果G是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若G不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多．本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法．首先注意到，若图G有奇数度节点，则G的奇数度节点必是偶数个．把奇数度节点分为若干对，每对节点之间在G中有相应的最短路，将这些最短路画在一起构成一个附加的边子集E．令//EGG，即把附加边子集/E迭加在原图G上形成一个多重图/G，这时G/中连接两个节点之间的边不止一条．显然/G是一个欧拉图，因而可以求出/G的欧拉回路．该欧拉回路不仅通过原图G中每条边，同时还通过E中的每条边，且均仅一次．邮递员问题的难点在于当G的奇数度节点较多时，可能有很多种配对方法，应怎样选择配对，能使相应的附加边子集/E的权数)(.E为最小？为此有下列定理．定理5设),(EVG为一个连通的赋权图，则使附加边子集/E的权数)(/E为最小的充分必要条件是/EG中任意边至多重复一次，且/EG中的任意回路中重复边的权数之和不大于该回路总权数的一半．必要性．用反证法．设存在一种奇节点集的配对，使其附加边子集/E权数)(/E为最小．若/EG中有一条边重复nn()2次，由于/EG为欧拉图，所以删去相应的二次重复边后仍为欧拉图．这样，相应的附加边子集的权数将减小，这与)(/E为最小的假设矛盾．这说明/E中的边均互不相同．其次，若/EG中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在/E中删去这些重复边（注意：这些边均在/E中），而代之以该回路的其余部分的边再重复一次．经过这种替代后所得到的边子集//E仍为附加子集，且)(///EE）（，又产生矛盾．充分性．设有两个附加边子集/E和//E，均使/EG/和//EG中每条边至多重复一次，统计与数理学院本科毕业论文设计6且每个回路中的重复边的权数和不大该回路权数的一半，我们来证明)()(///EE．首先注意到，由/E和//E不相同的部分组成的图（记为]\[//////）（EEEEG）是由一个或若干个欧拉子图所组成的．这是因为///EE中每个节点的度数均为偶数，而/E和//E的公共边数也是偶数，故]\[//////）（EEEEG中每个节点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成．]\[//////）（EEEEG的任何回路都由E/和E//中的边组成，而E/和E//在回路中的权数分别不大于该回路权数的一半，因而任何回路中属于/E中的权数之和与属于//E中的边数之和必定相等，所以)()(///EE．它就是最优附加边子集的权数，即/E和//E均为使附加边子集的权数达到最小的最优附加边子集.四数型分析由定理3可得一个寻找邮递员问题最优解的方法．现举例如下：A1A2A3A4B1B2B3B44431332333223图3例1知邮递员要投递的街道如图3示，试求最优邮路．先找出奇节点：1A，2A，3A，4A，1B，2B，3B，4B．奇节点进行配对，不妨把1A与1B，2A与2B，A3与B3，3A与3B配对，求其最短路．显然它不是最优解．下面我们根据定理3来进行调解．统计与数理学院本科毕业论文设计7A1A2A3A4B1B2B3B44431332333223图4第一次调整：删去多于一条的重复边，即3A与3B，4A与4B中的),,(34BA调整后，实际上成为1A与2B，2A与1B，3A与4A，3B与4B的配对，它们的最短路如图4示．A1A2A3A4B1B2B3B44431332333223图5第二次调整：发现在回路{1A，2A，2B，4A，3B4B，1B，1A}中重复边的权数和为11，大于该回路权数20的一半．因而调整时，把该回路的重复边删去，代之以重复其余部分，得图5．可以看出，实际上是调整为1A与2A，