1701009500
（3），其中Ci为Vi的导出子图G［Vi］中的最佳巡视回路，为Ci的权，i＝1，2，3，…，n，j＝1，2，3，…，n；
1701009501
1701009502
1701009503
（4）取最小。
1701009504
1701009505
1701009506
对于条件（3），设定为该分组的实际均衡度，α为最大允许均衡度，显然0≤α0≤1，α0越小，说明分组的均衡性越好。取定一个α后，α0与α满足条件（3）的分组是一个均衡分组。
1701009507
1701009508
条件（4）表示总巡视路线最短。
1701009509
1701009510
此问题包含两方面：第一，对顶点分组；第二，在每组中求最佳巡视回路，即为单个巡视员的最佳巡视回路问题。
1701009511
1701009512
由于单个巡视员的最佳巡视员回路问题不存在多项式时间内的精确算法，故多个巡视员的问题也不存在多项式时间内的精确算法。而图8-2中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图8-2进行初步划分后，求出各部分近似最佳巡视员回路的权，再进一步调整，使得各部分满足均衡性条件（3）。
1701009513
1701009514
从O点出发去其他点，要使路程较小应尽量走O点到该点的最短路，故用图论知识求出O点到其余顶点的最短路，这些最短路构成一棵以O为树根的树，将从O点出发的树枝称为干枝，如图8-2所示。
1701009515
1701009516
1701009517
1701009518
1701009519
图8-2 O点到任意点的最短路图（单位：km）
1701009520
1701009521
从图8-2中可以看出，从O点出发到其他点共有6条干枝，他们的名称分别为①、②、③、④、⑤和⑥。
1701009522
1701009523
根据实际工作的经验及上述分析，在分组时应遵从以下准则。
1701009524
1701009525
准则一：尽量使同一干枝及其分枝上的点分在同一组；
1701009526
1701009527
准则二：应将相邻的干枝上的点分在同一组；
1701009528
1701009529
准则三：尽量将长的干枝与短的干枝分在同一组。
1701009530
1701009531
由上述分组准则，我们找到两种分组形式如下。
1701009532
1701009533
分组一：（⑥，①），（②，③），（⑤，④）；
1701009534
1701009535
分组二：（①，②），（③，④），（⑤，⑥）。
1701009536
1701009537
显然⑥，①相对于②，③，分配是极不均匀的，故考虑分组二。
1701009538
1701009539
对分组二中每组顶点的生成子图，用加权图G（V，E）的最佳巡视路线的近似算法求出近似最优解及相应的巡视路线。使用加权图G（V，E）的最佳巡视路线的近似算法时，在每个子图所构造的完备图中，取一个尽量包含图8-2中树上的边的H圈作为其Step 2步输入的初始圈。
1701009540
1701009541
分组二的近似解如表8-1所示。
1701009542
1701009543
表8-1 分组二的近似解（单位：km）
1701009544
1701009545
1701009546
小组名称 路线 路线长度 路线的总长度 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-O 241.9 III O-R-29-Q-30-32-31-33-35-34-A-B-1-O 125.5 由表8-1可知，该分组的均衡度，所以此分法的均衡性很差。
1701009547
1701009548
为改善均衡性，将第Ⅱ组中的顶点C，2，3，D，4分给第Ⅲ组（顶点2为这两组的公共点），重新分组后的近似最优解如表8-2所示。
1701009549