信息与计算科学毕业论文1.doc

《信息与计算科学毕业论文1.doc》由会员分享，可在线阅读，更多相关《信息与计算科学毕业论文1.doc（15页珍藏版）》请在三一文库上搜索。

1、统计与数理学院本科毕业论文设计本科毕业论文(设计) 题目：中国邮递员问题综述学 院 统计与数理学院 专 业 信息与计算科学 班 级 2007级1班 学 号 20070534119 姓 名 高坤 指导教师 王 继 强 山东财政学院教务处制二O一一年五月中国邮递员问题综述高坤摘要：本文综合论述了运筹学中的中国邮递员问题，首先简介了该问题的起源，然后建立起该问题的图论模型，旨在使邮递员的投递线路最短，给出了算法和步骤，再借助lingo软件进行了实证分析. 中国邮递员问题的研究在网上交易和电子商务快速发展的今天尤其具有重要的现实意义.关键词：投递 一笔画 欧拉回路 最短路 Lingo一、引言图论是应用

2、十分广泛的运筹学分支，它已广泛的应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域.在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决.例如，在组织生产中，为完成某项任务，各工学之间怎么样衔接，才能使生产任务完成的又快又好.一个邮递员送信，要走完他负责投递的所有街道，完成任务后回到邮局，应该按照怎么样的路线走，才能使得走的路线最短.中国投递员问题是1960年我们从生产实际中提出的一个数学问题，它是从下述实际问题中抽象出来的：“一个投递员应该怎么选择一条线路，才能既把所有由他负责的信件都送到，而所走的路程又最短”. 在我们开始研究中国投递员问题以前，国外有人研究

3、过所谓旅行售货员的问题，即：“一个售货员要到个城市去售货，问他应该选择怎样的一条线路，才能既走遍所有城市，并且走的路程最短”. 这是一个著名的难题.当较大时，即使使用大型电子计算机，也很难解决.投递员面临的问题显然可以归纳为旅行售货员问题，事实上，只要把投递员必须送的每一个地点看成是一个城市就行了.但是一般来说，投递员每次要到约二、三百个地点送信，如果归纳为旅行售货员问题来解决，将是一个规模很大的问题，是无法解决的.但是，在仔细分析了投递员面临的问题后，我们发现这个问题具有一定的特点，即需要送信的地点一般都是比较密集的排列在街道上的，因此，实际上，我们称这个问题为“最短投递线路问题”，1965

4、年后国外称之为“中国投递员问题”.二、概念与原理一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题用图论的述语，在一个连通的赋权图中，要寻找一条回路，使该回路包含中的每条边至少一次，且该回路的权数最小也就是说要从包含的每条边的回路中找一条权数最小的回路在实际生活中，人们为了反映一些对象之间的关系，常常会在纸上用点和线画出各种各样的示意图. 例如：8世纪时，欧洲有一

5、个风景秀丽的小城哥尼斯堡, 那里有七座桥.如图1所示：河中的小岛与河的左岸、右岸各有两座桥相连结，河中两支流间的陆地与、各有一座桥相连结.问：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？这个例子是历史上非常有名的哥尼斯堡7桥问题.哥尼斯堡现在是立陶宛共和国的一个城市，图1是当地奈发夫岛附近的地域图，此例子就是当地人民中间流传久远的一个难题.直到1736年，数学家欧拉首次系统研究并完全解决了这类问题.图1七桥问题引起了著名数学家欧拉（17071783）的关注.他把具体七桥布局化归为图2所示的简单图形，于是，七桥问题就变成一个一笔划问题：怎样才能从、中的某一点出发，一笔划出这个

6、简单图形（即笔不离开纸，而且、各条线只画一次不准重复），并且最后返回起点？图2一笔划出的图形中的各点或者都是与偶数条线相连的点，或者其中只有两个点与奇数条线相连.欧拉定理: 如果一个网络是连通的并且奇顶点的个数等于0或2，那么它可以一笔划出，否则它不可以一笔划出.定义 经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路,含Euler回路的图叫做Euler图.直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点.定理1（1）是Euler图的充分必要条件是连通且每顶点皆偶次.（2）是Euler图的充分必要条件是连通且

7、，是圈，.（3）中有Euler迹的充要条件是连通且至多有两个奇次点.另外一种表述：定理2 对连通图G（V，E），下列条件是相互等价的： （1）G是一个欧拉图； （2）G的每一个节点的度数都是偶数； （3）G的边集合E可以分解为若干个回路的并如果一幅图是由点和线连接组成，那么与奇数条线相连的点叫“奇点”，与偶数条线相连的点叫“偶点”三、运作模式一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此

8、在国际上称之为中国邮递员问题 用图论的述语，在一个连通的赋权图中，要寻找一条回路，使该回路包含中的每条边至少一次，且该回路的权数最小也就是说要从包含的每条边的回路中找一条权数最小的回路如果是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多本次的要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法所谓欧拉路与哥尼斯堡7桥问题相联系的在哥尼斯堡7桥问题中，欧拉证明了不存在这样的回路，使它经过图中每条边且只经过一次又回到起始点与此相反，设为一个图，若存在一条回路，使它经过图中每条边且只经过一次又回到起始点，就称这种回路为欧拉

9、回路，并称图为欧拉图在一个图中，连接一个节点的边数称为该节点的度数对欧拉图，我们有下列结果：定理3 下列条件是相互等价的： （1）是一个欧拉图； （2）的每一个节点的度数都是偶数； （3）的边集合可以分解为若干个回路的并 证明 ： 已知为欧拉图，则必存在一个欧拉回路回路中的节点都是偶度数 设中每一个节点的度数均为偶数若能找到一个回路使，则结论成立否则，令，由上每个节点的度数均为偶数，则中的每个节点的度数亦均为偶数于是在必存在另一个回路令，由于为有限图，上述过程经过有限步，最后必得一个回路使 上各节点的度数均为零，即这样就得到的一个分解 设，其中（I=1,2,r）均为回路由于为连通图，对任意回路

10、,必存在另一个回路与之相连，即与存在共同的节点现在我们从图G的任意节点出发，沿着所在的回路走，每走到一个共同的节点处，就转向另一个回路，这样一直走下去就可走遍的每条边且只走过一次,最后回到原出发节点，即为一个欧拉图利用定理1去判断一个连通图是否为欧拉图比较容易，但要找出欧拉回路，当连通图比较复杂时就不太容易了下面介绍一种求欧拉回路的算法即：弗罗莱算法算法步骤如下：（1）任取起始点 （2）设路已选出，则从E中选出边，使与相连，除非没有其它选择，仍应为连通的 （3）重复步骤（2），直至不能进行下去为止定理4 有向图存在欧拉回路的充分必要条件是对任意节点，进入该节点边数（进数）与离开该点的边数（出数

11、）相等 如果是欧拉图，则很容易由弗罗莱算法求出一个欧拉回路，但是若不是欧拉图，即存在奇度数的节点，则中国由递员问题的解决要困难得多本节的主要目标是给出在有奇度数节点的连通图中寻找最小权数的回路的方法首先注意到，若图有奇数度节点，则的奇数度节点必是偶数个把奇数度节点分为若干对，每对节点之间在中有相应的最短路，将这些最短路画在一起构成一个附加的边子集令，即把附加边子集迭加在原图上形成一个多重图，这时G/中连接两个节点之间的边不止一条显然是一个欧拉图，因而可以求出的欧拉回路该欧拉回路不仅通过原图中每条边，同时还通过中的每条边，且均仅一次邮递员问题的难点在于当的奇数度节点较多时，可能有很多种配对方法，

12、应怎样选择配对，能使相应的附加边子集 的权数为最小？为此有下列定理 定理 5 设为一个连通的赋权图，则使附加边子集的权数为最小的充分必要条件是中任意边至多重复一次，且中的任意回路中重复边的权数之和不大于该回路总权数的一半必要性用反证法设存在一种奇节点集的配对，使其附加边子集权数 为最小若中有一条边重复次，由于为欧拉图，所以删去相应的二次重复边后仍为欧拉图这样，相应的附加边子集的权数将减小，这与为最小的假设矛盾这说明中的边均互不相同 其次，若中存在一个回路，使它的重复边的权数之和大于该回路总权数的一半，则在中删去这些重复边（注意：这些边均在中），而代之以该回路的其余部分的边再重复一次经过这种替代

13、后所得到的边子集仍为附加子集，且，又产生矛盾 充分性设有两个附加边子集和，均使/和中每条边至多重复一次，且每个回路中的重复边的权数和不大该回路权数的一半，我们来证明首先注意到，由和不相同的部分组成的图（记为）是由一个或若干个欧拉子图所组成的这是因为中每个节点的度数均为偶数，而和的公共边数也是偶数，故中每个节点的度数仍为偶数，所以它若为连通图时是一个欧拉图；若为非连通图时则由若干个欧拉子图组成的任何回路都由E/和E/中的边组成，而E/和E/在回路中的权数分别不大于该回路权数的一半，因而任何回路中属于中的权数之和与属于中的边数之和必定相等，所以它就是最优附加边子集的权数，即和均为使附加边子集的权数

14、达到最小的最优附加边子集.四 数型分析 由定理3可得一个寻找邮递员问题最优解的方法现举例如下： 图3例1 知邮递员要投递的街道如图3示，试求最优邮路先找出奇节点：，奇节点进行配对，不妨把与，与，A3与B3，与配对，求其最短路显然它不是最优解下面我们根据定理3来进行调解图4第一次调整：删去多于一条的重复边，即与，与中的调整后，实际上成为与，与，与，与的配对，它们的最短路如图4示图5第二次调整：发现在回路，中重复边的权数和为11，大于该回路权数20的一半因而调整时，把该回路的重复边删去，代之以重复其余部分，得图5可以看出，实际上是调整为与，与，与，与配对图6第三次调整：在图5中发现回路，中重复边的

15、权数和为7，大于该回路权数10的一半，因而删去原重复边（，）和（，），而添加（，），得到图6进行检查发现，既没有多于一条的重复边，也没有任何回路使其重复边的权数之和大于该回路的一半，因此图6就是最优的附加边子集，而为欧拉图，因此，可以求得最优的路线为.五 优化模型 上述的邮递员问题，假定了邮递员的投递范围内的每条街道的上行和下行使没有差别的，而在实际信件的投递过程中是不可能的，如果遇到单行线街道、街道有一定的坡度、街道两边不能单行中同时投递等问题.这样的问题称之为广义的中国邮递员问题.这一广义的中国邮递员问题可以抽象为一个有向图问题. 类似于前面描述的邮递员问题（称之为传统的邮递员问题），广义

16、的邮递员问题可以综述为：给定一个连通有向图每个弧上有非负权，需要寻找的一个回路，它过每个弧至少一次，且使得总权最小.对于广义的中国邮递员问题，添加弧的个数至多1条有时已经不再可行，即需要添加多条弧，才能使对应的连通有向图的任一定点的进向弧数与出向弧数相同，从而使,存在回路（回路）.在此，如,则称弧是顶点的进向弧，同时也是的出向弧.可以证明，如的顶点数为，则每条弧上至多增加条添加弧，即可实现各顶点的进项弧数与出向弧数相等.根据以上分析，对于的每条弧定义一正整数变量，表示弧上增加了条添加弧，由此形成一个有向图.类似以上的分析，可以有广义的中国邮递员显示整数规划模型（）: min s.t.通过这一模

17、型的求解，可以得到广义的中国邮递员问题的最优投递路线.考虑下图的中国邮递员问题：图77图8根据前面的模型讨论，这一数值例式邮递员问题对应的整数规划模型如下： lingo程序如下：minZ=2*(x18+x81)+4*(x87+x78)+5*(x12+x21)+3*(x89+x98)+6*(x29+x92)+3*(x67+x76)+4*(x69+x96)+5*(x32+x23)+4*(x94+x49)+4*(x56+x65)+9*(x43+x34)+4*(x54+x45);x21+x81-x12-x18=0;x12+x92+x32-x21-x29-x23=0;x23+x43-x32-x34=0;

18、x34+x94+x54-x43-x49-x45=0;x65+x45-x56-x54=0;x76+x96+x56-x67-x69-x65=0;x67+x87-x76-x78=0;x18+x78+x98-x81-x87-x89=0;x29+x49+x69+x89-x92-x94-x96-x98=0;x18+x81=1 ;x87+x78=1;x12+x21=1;x89+x98=1;x67+x76=1;x29+x92=1;x96+x69=1;x23+x32=1;X94+X49=1;X56+X65=1;X43+X34=1;X45+X54=1;表9运行lingo9.0得到结果如下Feasible solu

19、tion found.Total solver iterations: 6 Variable Value MINZ 88.00000 X18 0.000000 X81 1.000000 X87 2.000000 X78 0.000000 X12 1.000000 X21 0.000000 X89 0.000000 X98 3.000000 X29 0.000000 X92 1.000000 X67 0.000000 X76 2.000000 X69 1.000000 X96 0.000000 X32 0.000000 X23 2.000000 X94 0.000000 X49 3.000000

20、 X56 0.000000 X65 1.000000 X43 0.000000 X34 2.000000 X54 1.000000 X45 0.000000 Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 1.000000 13 0.000000 14 2.000000 15 1.000000 16 0.000000 17 0.000000 18 1.

21、000000 19 2.000000 20 0.000000 21 1.000000 22 0.000000 所以这一问题的最优解是其它，最小权重为88.假定邮局在定点V,则有如下最优投递路线：注意这一问题的最优投递路线不唯一.同理可以求得邮局从任何一丁点出发时的最优投递路线.六 结束语现在我国经济正处于高速发展的过程中，尤其是信息产业的快速发展更是日新月异，而在这其中，电子商务行业更是异军突起，发展迅猛，以淘宝网、当当网、卓越网等为代表的网站更是带动了第三产业的迅猛发展，而与之相关的邮递产业也就提出了更加严格的考验，而如何更加快速、及时、准确的把信件送到客户的手中，更是邮递行业竞争的激烈点，

22、所以说研究邮递员问题就显得会很有现实意义.当然，在本文之外还有很多涉及此问题的相关论题，我们还要不断努力，不断学习，为我国的邮递事业进到一点贡献.参考文献：1管梅谷 奇偶点图上作业法M.数学学报, 1960.3.2管梅谷 邮递员问题综述M.数学研究与评论1965.53李玮 、王雷 中国邮递员问题的DNA计算M 中国教育出版,2009.64许志国、桂湘云 运筹学（第三版）M清华大学出版社2008.75韩中庚. 用运筹学模型、方法计算M.清华大学出版,2007.96哈拉里 图论 M 上海科技出版社 1980.97李念祖 关于中国邮递员问题的最有完全子图算法社J 2009.19(07)8吴杰 求解中

23、国邮递员问题的一种思路J 科技资讯 2007,169冯俊文 中国邮递员问题的整数规划模型J ,2010.1210 金毅 对中国邮递员的理性分析 J, 科技经济市场 2009.5A review of the Chinese postman problem Gao KunAbstract: This article gives a conmprehensive review of the Chinese postman problem(CPP), the use of operations research principles of graph theory, Euler circuit, b

24、y the Konigsberg problem associated with the first issue of a stroke, the postman problem into a graph theory-related model, using the shortest Road principle of making the shortest postmans delivery routes, and further discussed the actual situation in China generalized directed graph based on the

25、Chinese postman problem, the corresponding model, then study the Chinese postman problem. This article is mainly based on modern internet proposed The rapid development of trade, mail efficiency has become a highly competitive industry, this question will be more importmant. Otherwise, there has man

26、y questions besides this article , so we should continue to learning and do our best to contribute to our post bussiness.Keywords: Post, A Stroke, Euler Circult, Shortest Path, Lingo本文综合论述了运筹学中的中国邮递员问题，首先简介了该问题的起源，然后建立起该问题的图论模型，旨在使邮递员的投递线路最短，给出了算法和步骤，再借助lingo软件进行了实证分析. 中国邮递员问题的研究在网上交易和电子商务快速发展的今天尤其具有重要的现实意义.14