信息与计算科学毕业论文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/在回路中的权数分别不大于该回路权数的一半,因而任何回路中属于中的权数之和与属于中的边数之和必定相等,所以它就是最优附加边子集的权数,即和均为使附加边子集的权数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息 计算 科学 毕业论文
链接地址:https://www.31doc.com/p-3261322.html