《行遍性问题》PPT课件

《《行遍性问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4讲行遍性问题一、中国邮递员问题二、推销员问题三、建模案例：最佳灾情巡视路线（一）欧拉图（二）中国邮递员问题（一）哈密尔顿图（二）推销员问题V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中．割边的定义：设G连通，eE(G),若从G中删除边e后，图G-{e}不连通，则称边e为图G的割边．e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e

2、3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图中国邮递员问题-定义中国邮递员问题-算法Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．解决这类问题的一般方法是，在一些点对

3、之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．哈密尔顿图推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．推销员问题是NP-完备问题，即没有多项式时间算法。若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一

4、次的最短闭通路问题．定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长4推销员问题近似算法：二边逐次修正法：例对以下完备图，用二边逐次修正法求较优H圈．图a图b图c图d例:从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之

5、间的航线距离如下表：LMNPaPeTLinf5635215160M56inf21577870N3521inf366868Pa215736inf5161Pe51786851inf13T6070686113inf例:有7个人,A会讲英语,B会讲英语和汉语,C会讲英语、意大利语和俄语,D会讲日语和汉语,E会讲德语和意大利语,F会讲法语、日语和俄语,G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?ABCDEFGACEGFDBA是一条哈密顿回路,按此顺序就坐即可.解:作无向图,每人是一个顶点,2人之间有边他

6、们有共同语言.ABCDEFG英汉意俄日德法建模实例　灾情巡视路线图为某乡，（镇），村公路网示意图，公路边的数字为该路段的公里数。有一年夏天该县遭受水灾。为考察灾情，组织自救，县领导决定，带领有关部门负责人到全县各乡，（镇），村巡视。巡视路线指从县政府所在地出发，走遍各乡，镇，村，又回到县政府所在地的路线。（1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。（2）假定各巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间T=1小时，汽车行驶速度v=35千米/小时。要在24小时内完成巡视，至少应分几组：给出这种分组下

7、你认为最佳的巡视路线。（3）在上述关于T，t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。（4）若巡视组数已定（如三组），要求尽快完成巡视，讨论T,t和v改变时最佳巡视路线的影响。以下我们参考当年的优秀答卷对这一问题作一分析。一、关于问题的数学模型本题给出了某县的道路交通网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的普遍性问题，也就是用若干条闭链覆盖图上的所在顶点，关使某些指标达到最优。点的遍历性问题在图论属于哈密顿问题和旅行推

8、销员问题。本题所求得分组巡视的最佳路线与多个旅行推销员问题类似但也有不同，因为还有均衡性的要求。由于旅行推销员问题属于NP-完全类，本题的规模比较大（包括县城共有53个点），所以要想求出真正的最优解是不现实的，为此只能针对具体问题，采