文档介绍：)98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、,走遍各乡(镇)、村,”中的前两个问题是这样的:1)若分三组(路)巡视,)假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/,至少应分几组;)问题分析:本题给出了某县的公路网络图,要求的是在不同的条件下,(镇)或村看作一个图的顶点,各乡镇、村之间的公路看作此图对应顶点间的边,各条再回到点O,使得总权(路程或时间)(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化图论中一类称之为旅行售货员问题,即在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次如第一问是三个旅行售货员问题,第二问是四本题是旅行售货员问题的延伸-,也就是m条众所周知,旅行售货员问题属于NP完全问题,,经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链(闭迹).,想找到解决此类问题的一般方法是不现实的,,行遍所有顶点至少一次再回回到点O,使得总权(路程或时时间)最小,—完全问题,采用一种近似算法求其一个近似最优解,:1)用图论软件包求出G中任意两个顶点间的最短路,构造出完全图2)输入图的一个初始H圈;3)用对角线完全算法(见[23])产生一个初始圈;4)随机搜索出中若干个H圈,例如2000个;5)对第2),3),4)步所得的每个H圈,用二边逐次修正法进行优化,得到近似最优H圈;6)在第5)步求出的所有H圈中,找出权最小的一个,,故本算法第2),3),4)步分别用三种方法产生初始圈,,)此问题包含两方面:a)对顶点分组,b)在每组中求(单个售货员),为53个,我们只能去寻求一种较合理的划分准则,对图1进行粗步划分后,求出各部分的近似最佳旅行售货员回路的权,再进一进一步进行调整,使得各部分满足均衡性条件3).从O点出发去其它点,.