将公路网图中,每个乡(镇)或村看作图中的一个节点,各乡(镇)、村之 间的公路看作图中对应节点间的边,各条公路的长度(或行驶时间)看作对应边 上的权,所给公路网就转化为加权网络图,问题就转化为在给定的加权网络图中 寻找从给定点O出发,行遍所有顶点至少一次再回到O点,使得总权(路程或 时间)最小,此即最佳推销员回路问题 在加权图G中求最佳推销员回路问题是NP一完全问题,我们采用一种近似 算法求出该问题的一个近似最优解,来代替最优解,算法如下: 算法一求加权图G(V,E)的最佳推销员回路的近似算法: 用图论软件包求出G中任意两个顶点间的最短路,构造出完备图 G'(,E), V(x,yEE,, o(x, y)=Mind(x,y); 2.输入图G的一个初始H圈; 3.用对角线完全算法(见[23])产生一个初始H圈; 4.随机搜索出G中若干个H圈,例如2000个; 5.对第2、3、4步所得的每个H圈,用二边还次修正法进行优化,得到近 似最佳H圈; 6.在第5步求出的所有H圈中,找出权最小的一个,此即要找的最佳H圈 的近似解. 由于二边逐次修正法的结果与初始圈有关,故本算法第2、3、4步分别用三 种方法产生初始圈,以保证能得到较优的计算结果 问题一若分为三组巡视,设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个推销员的最佳推销员回路问题即在加权图G中求顶点集的 划分1,n2Vn,将G分成n个生成子图2]n,使得 1)顶点O∈V i=1,2,3.n (2) (3)Maxlo(c)-aCj ≤a’其中c为的导出子图c]中的最佳推销员 回路,o(C)为C的权,i,j1,2,3.……n (4)∑o(C1)=M 定义称。Mxp(C)-o(c 为该分组的实际均衡度a为最大容许均 Maxo(c 衡度 显然0≤a0≤1,a越小,说明分组的均衡性越好取定一个a后,a0与a满 足条件(3)的分组是一个均衡分组条件(4)表示总巡视路线最短 此问题包含两方面:第一、对顶点分组;第二、在每组中求最佳推销员回路, 即为单个推销员的最佳推销员问题 由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法,故 多个推销员的问题也不存在多项式时间内的精确算法而图中节点数较多,为53将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之 间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边 上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中 寻找从给定点 O 出发，行遍所有顶点至少一次再回到 O 点，使得总权（路程或 时间）最小，此即最佳推销员回路问题. 在加权图 G 中求最佳推销员回路问题是 NP—完全问题，我们采用一种近似 算法求出该问题的一个近似最优解，来代替最优解，算法如下： 算法一 求加权图 G（V，E）的最佳推销员回路的近似算法： 1． 用图论软件包求出 G 中任意两个顶点间的最短路，构造出完备图 G(V, E) ， (x, y)E， (x y) Mind (x y) G  , = , ； 2． 输入图 G 的一个初始 H 圈； 3． 用对角线完全算法（见[23]）产生一个初始 H 圈； 4． 随机搜索出 G 中若干个 H 圈，例如 2000 个； 5． 对第 2、3、4 步所得的每个 H 圈，用二边逐次修正法进行优化，得到近 似最佳 H 圈； 6． 在第 5 步求出的所有 H 圈中，找出权最小的一个，此即要找的最佳 H圈 的近似解. 由于二边逐次修正法的结果与初始圈有关，故本算法第 2、3、4 步分别用三 种方法产生初始圈，以保证能得到较优的计算结果. 问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个推销员的最佳推销员回路问题.即在加权图 G 中求顶点集 V 的 划分 V V Vn , ,....... 1 2 ，将 G 分成 n 个生成子图       G V G V G Vn , ,...... 1 2 ，使得 （1）顶点 O Vi i=1，2，3……n （2） V V (G) n i i = =  1 （3） ( ) ( ) ( )      − i i i j i j Max C Max C C , ，其中 Ci 为 Vi 的导出子图   G Vi 中的最佳推销员 回路， ( )  Ci 为 Ci 的权，i，j=1，2，3……n （4） (C ) Min n i  i = =1  定义 称 ( ) ( ) ( ) i i i j i j Max C Max C C     − = , 0 为该分组的实际均衡度. 为最大容许均 衡度. 显然 0 0 1， 0 越小，说明分组的均衡性越好.取定一个  后，  0 与  满 足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短. 此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路， 即为单个推销员的最佳推销员问题. 由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故 多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为 53