分近似最佳推销员回路的权,再进一步调整,使得各部分满足均衡性条件(3) 218 05 14 ① 10 图2O点到任意点的最短路图(单位:km) 从O点出发去其他点,要使路程较小应尽量走O点到该点的最短路故用图 论软件包求出O点到其余顶点的最短路,这些最短路构成一棵以O为树根的树, 将从O点出发的树枝称为干枝,见图2,从图中可以看出,从O点出发到其它 点共有6条干枝,他们的名称分别为①,②,③,④,⑤,⑥ 根据实际工作的经验及上述分析,在分组时应遵从以下准则 准则一:尽量使同一干枝及其分枝上的点分在同一组 准则二:应将相邻的干枝上的点分在同一组 准则三:尽量将长的干枝与短的干枝分在同一组 由上述分组准则,我们找到两种分组形式如下: 分组一:(⑥,①),(②,③),(⑤,④); 分组二:⑨①,②),(③,④),(⑤,⑥) 显然分组一的方法极不均衡,故考虑分组二 对分组二中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路 线使用算法一时,在每个子图所构造的完备图中,取一个尽量包含图2中树上 的边的H圈作为其第2步输入的初始圈 分组二的近似解见表1 表1(单位:km) 小组 路线 名称 路 线 总路线长度总长 O-P28-2726-N-24-23-22-17-16-1-15--18-K 21-20-25M0 191.1 0-2-56-L-19J-11-G-13-14H-12-F-10-F-9 558.5 E-7-E 2419 -8-4-D3-C OR-29-Q30-32-31-33-35-34A-B-1-0 125.5分近似最佳推销员回路的权，再进一步调整，使得各部分满足均衡性条件（3）. 从 O点出发去其他点，要使路程较小应尽量走 O点到该点的最短路.故用图 论软件包求出 O 点到其余顶点的最短路，这些最短路构成一棵以 O为树根的树， 将从 O 点出发的树枝称为干枝，见图 2，从图中可以看出，从 O 点出发到其它 点共有 6 条干枝，他们的名称分别为①，②，③，④，⑤，⑥. 根据实际工作的经验及上述分析，在分组时应遵从以下准则： 准则一：尽量使同一干枝及其分枝上的点分在同一组； 准则二：应将相邻的干枝上的点分在同一组； 准则三：尽量将长的干枝与短的干枝分在同一组. 由上述分组准则，我们找到两种分组形式如下： 分组一：（⑥，①），（②，③），（⑤，④）； 分组二：（①，②），（③，④），（⑤，⑥）． 显然分组一的方法极不均衡，故考虑分组二. 对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路 线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图 2 中树上 的边的 H 圈作为其第 2 步输入的初始圈. 分组二的近似解见表 1. 表 1（单位：km） 小组 名称 路 线 总路线长度 路线的 总长度 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 III O-R-29-Q-30-32-31-33-35-34-A-B-1-O 125.5 图 2 O 点到任意点的最短路图（单位：km）