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