个,我们只能去寻求一种较合理的划分准则,对图11-9进行粗步划分后,求 出各部分的近似最佳推销员回路的权,再进一步进行调整,使得各部分满足均衡 性条件(3). 并、E03 32 图11-10O点到任意点的最短路图(单位:公里) 从O点出发去其它点,要使路程较小应尽量走O点到该点的最短路故用图 论软件包求出O点到其余顶点的最短路,这些最短路构成一棵O为树根的树, 将从O点出发的树枝称为干枝,见图11-10,从图中可以看出,从O点出发 到其它点共有6条干枝,它们的名称分别为①,②,⑧,④⑤,回. 根据实际工作的经验及上述分析,在分组时应遵从以下准则: 准则一:尽量使同一干枝上及其分枝上的点分在同一组; 准则二:应将相邻的干枝上的点分在同一组; 准则三:尽量将长的干枝与短的干枝分在同一组 由上述分组准则,我们找到两种分组形式如下: 分组一:(⑥,①),(②,③),(⑤,④) 分组二:⑨①,②),(③,④),(⑤,⑥) 显然分组一的方法极不均衡,故考虑分组二 对分组二中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路 线使用算法一时,在每个子图所构造的完备图中,取一个尽量包含图11-10中树 上的边的H圖圈作为其第2步输入的初始圈 分组二的近似解见表1 表1(单位:公里) 小组 路线 名称 路 线 总路线长度总长度 O-P-28-27-26-N-2423-22-17-16-1-15--18-K 21-20-25-M0 0-2-5-6-L-19-J-l1-G-13-14H-12-F-10-F9 558.5 E-7-E 241 -8-4-D3-C个，我们只能去寻求一种较合理的划分准则，对图１1－9 进行粗步划分后，求 出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡 性条件（3）. 从 O点出发去其它点，要使路程较小应尽量走 O点到该点的最短路.故用图 论软件包求出 O 点到其余顶点的最短路，这些最短路构成一棵 O 为树根的树， 将从 O点出发的树枝称为干枝，见图１１－１0，从图中可以看出，从 O点出发 到其它点共有 6 条干枝，它们的名称分别为①，②，③，④，⑤，⑥. 根据实际工作的经验及上述分析，在分组时应遵从以下准则： 准则一：尽量使同一干枝上及其分枝上的点分在同一组； 准则二：应将相邻的干枝上的点分在同一组； 准则三：尽量将长的干枝与短的干枝分在同一组. 由上述分组准则，我们找到两种分组形式如下： 分组一：（⑥，①），（②，③），（⑤，④） 分组二：（①，②），（③，④），（⑤，⑥） 显然分组一的方法极不均衡，故考虑分组二. 对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路 线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图 11-10 中树 上的边的 H 圈作为其第 2 步输入的初始圈. 分组二的近似解见表 1. 表 1（单位：公里） 小组 名称 路 线 总路线长度 路线的 总长度 I O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K -21-20-25-M-O 191.1 558.5 II O-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9- E-7-E -8-4-D-3-C 241.9 图 11-10 O 点到任意点的最短路图（单位：公里）