文档介绍：)98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的:今年(198年)夏天某县遭受水灾为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线1)若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线2)假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/,至少应分几组;给出这种分组下最佳的巡视路线★政府雁在地乡())问题分析:本题给出了某县的公路网络图,要求的是在不同的条件下,灾情巡视的最佳分组方案和路线将每个乡(镇)或村看作一个图的顶点,各乡镇、村之间的公路看作此图对应顶点间的边,各条公路的长度(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化图论中一类称之为旅行售货员问题,即在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回到点O,使得总权(路程或时间)最小本题是旅行售货员问题的延伸一多旅行售货员问题本题所求的分组巡视的最佳路线,也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链(闭迹)如第一问是三个旅行售货员问题,第二问是四个旅行售货员问题众所周知,旅行售货员问题属于NP完全问题,即求解没有多项式时间算法显然本问题更应属于NP完全问题有鉴于此,定要针对问题的实际特点寻找简便方法,想找到解决此类问题的一般方法是不现实的,,使得x。总权(路程或时时间)最小,即最佳旅行售货员问题因二边逐次修正法的结果与初始圈有关,故本算法第2),3),4)步分别用三种方法产生初始圈,以保证能得到较优的计算结果算法一求加权图的最佳旅行售货员回路近似算法:1)用图论软件包求出G中任意两个顶点间的最短路,构造出完全图G′=(V,E'),V(x,y)∈E,o(x,y)mindG(x,y);2)输入图G′的一个初始H圈;3)用对角线完全算法(见[23)产生一个初始圈;4)随机搜索出G中若干个H圈,例如2000个;5)对第2),3),4)步所得的每个H圈,用二边逐次修正法进行优化,得到近似最优H圈;6)在第5)步求出的所有H圈中,找出权最小的一个,此即要找的最优H圈的近似解问题一若分为三组巡视,设计总路程最短且各组尽可能均衡的巡视路线此问题是多个售货员的最佳旅行售货员问题即在加权图G中求顶点集v的划分V,V2Vvn,将G分成n个生成子图Gv]GV2]…GVn],使得1)顶点O∈v,i=12,3,…,)∪v=v(Gmaxlo(Ci)-o(c)I≤a,其中C;为V的导出(C;)子图GV中的最佳旅行售货员回路,ω(C;)为C;的权,i,j=1,2,3…,)∑o(C)=mini=1maxlo(ci)-o(c)定义称a0为该分组的实际maxo(Ci)≤ao≤1,α越小,,a0与a满足条件3)):a)对顶点分组,b)在每组中求(单个售货员)最佳旅行售货员回路霰个售员的最佳旅售货员回路间不存在多项式时间内的精确算法而图中节点数较多,为53个,我们只能去寻求一种较合理的划分准则,对图1进行粗步划分后求出各部分的近似最佳旅行售货员回路的权,再进一进一步进行调整,使得各部分满足均衡性条件3)从O点出发去其它点,要使路程较小应尽量走O点到该点的最短路故用软件包求出O点到其余顶点的最短路这些最短路构成一棵O为树根的树将从O点出发的树枝称为干枝