中国邮路问题ppt课件_第1页
中国邮路问题ppt课件_第2页
中国邮路问题ppt课件_第3页
中国邮路问题ppt课件_第4页
中国邮路问题ppt课件_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

4.2、中国邮路问题,邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。,1、提出问题,返回结束,上图表示从R1-R15个街道交叉点，街道上的数字表示该街道的长度，单位为米。,1,首先把这个实际问题转换成一个非负赋权图G，G的顶点代表街与街之间的交叉路口和终端，两个顶点相邻当且仅当这两点所对应的路口有直通街道而中间不通过其他路口，每条边的权是这条边所对应街道的长度。G的通过每条边至少一次的闭途径称为G的环游。具有最小权的环游称为G的最优环游，则中国邮路问题就是要在赋权图G中找一条最优环游。,2、分析问题,2,街道结构图,由上构造右图,3,3、解决问题,返回结束,寻找Euler图的最优环游的基本思路：（1）用双倍边方法求的一个Euler赋权母图，使达到最小。（2）用Fleury算法求得的Euler环游,就是图的环游；,4,定理4.2.1（管梅谷，1960）设是一个连通的赋权图，是的一个Euler赋权生成母图，则当且仅当没有重复数大于2的边。并且的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半。,返回结束,5,奇偶点图上作业法（求最优环游算法）：,(1)把中度为奇数的顶点两两配对，记为。对每个，中取一条路，将上的每一条边都添加一条边，从而得到的一个赋权Euler生成母图。,(2)去掉中关于的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。,(4)用Fleury算法求的Euler环游。,(3)检查的每一个回路，如果某个回路上多重边的权和超过此回路权和的一半，则将进行调整：删除，的边重数增加1。,6,7,解：根据上述算法(1)，把和配对，和配对，取，并对中每条边各添加一条边；又取，并对中每条边各添加一条边。得图(b).依次按算法，得到图(c),(d),(e),8,奇偶点图上作业法缺陷：奇偶点图上作业法需要检查图中的每个回路。随着顶点个数和边数增加，回路个数增加。如下图一，图二。图一回路超过150个，图二回路至少有上千个。,9,思考：如何求恰好有两个奇点的赋权图的最优环游？,设恰好有两个奇点和，则可以利用2.2节求出的一条最短路，在中只要把中的每一条边中再添加一条边，加上权就可得Eluer图。可以证明的Elu
人人文库> 全部分类> 教育资料 > 作文作品

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论