1701009470
1701009471
求加权图G（V，E）的最佳巡视路线的近似算法。
1701009472
1701009473
1701009474
1701009475
Step1：用图论软件包求出G中任意两个顶点间的最短路，构造出完备图；
1701009476
1701009477
Step2：输入图G′的一个初始H圈；
1701009478
1701009479
Step3：用对角线完全算法产生一个初始H圈；
1701009480
1701009481
Step4：随机搜索出GG′中若干个H圈，例如2000个；
1701009482
1701009483
Step5：对Step2、Step3、Step4步所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈；
1701009484
1701009485
Step6：在Step5步求出的所有H圈中，找出圈最小的一个，此即要找的最佳H圈的近似解。
1701009486
1701009487
由于二边逐次修正法的结果与初始圈有关，故Step2、Step3、Step4步分别用三种方法产生初始圈，以保证能得到较优的计算结果。
1701009488
1701009489
1701009490
若分为3组巡视，设计总路程最短且各组尽可能均衡的巡视路线。此问题是多个巡视员的最佳巡视回路问题，即在加权图G中求顶点集V的划分V1，V2…，Vn，将G分成n个生成子图，使得：
1701009491
1701009492
1701009493
（1）顶点；
1701009494
1701009495
1701009496
（2）；
1701009497
1701009498
1701009499
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）