-（大学课件）数学建模与数学实验-行遍性问题-PPT.ppt

1、 行行 遍遍 性性 问问 题题数学建模与数学实验数学建模与数学实验docin/sundae_meng行行 遍遍 性性 问问 题题一、中一、中 国国 邮邮 递递 员员 问问 题题二、推二、推 销销 员员 问问 题题三、建模案例：最佳灾情巡视路线三、建模案例：最佳灾情巡视路线（一）（一）欧欧 拉拉 图图（二）（二）中中 国国 邮邮 递递 员员 问问 题题（一）（一）哈哈 密密 尔尔 顿顿 图图（二）（二）推推 销销 员员 问问 题题docin/sundae_mengdocin/sundae_meng 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9割边G的边 是割边的充要条件是 不含

2、在G的圈中 割边的定义割边的定义：设G连通，E(G),若从G中删除边 后，图G-不连通，则称边 为图G的割边eeeeeevvvvvvveeeeeeeeedocin/sundae_meng e3 v1 v2 v3 v4e1e2e4 e5e6欧欧 拉拉 图图 e3 v1 v2 v3 v4 e1e 2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1docin/sundae_menge3 v1 v2 v3v4e1e2e4 e5e3 v1 v2 v3v 4 e1 e2e4

3、 e5e6欧拉图 非欧拉图返回返回docin/sundae_meng中国邮递员问题中国邮递员问题-定义定义 邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是中中国国邮邮递递员员问问题题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最最佳佳巡巡回回docin/sundae_meng中国邮递员问题中国邮递员问题-算法算法 Fleury算法基本思想算法基本思想：从任一点出发，每当访问一条

4、边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有边可选择为止.docin/sundae_meng v7e3 v1v2 v3v4e1 e2e4 e5 v5 e6e6 e 7 e8 e9e10docin/sundae_meng 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小docin/sundae_mengv7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9docin/su

5、ndae_mengEdm onds 最最 小小 对对 集集 算算 法法：docin/sundae_meng算算法法步步骤骤：（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对docin/sundae_meng例例 求右图所示投递区的 一条最佳 邮递路线 1图中有v4、v7、v8、v9四个奇次顶点用 Floyd 算法求出它们之间的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv返回返回d

6、ocin/sundae_meng哈哈 密密 尔尔 顿顿 图图返回返回docin/sundae_meng推销员问题推销员问题-定义定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题docin/sundae_meng定义定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4docin/sundae_mengdocin/sundae_meng推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：docin/sundae_meng例例对以下完备图，用二边逐次修正法求较优H圈docin/sundae_meng返回返回docin/sundae_meng