1701009461
1701009462
如图8-1所示，将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给出的公路网就转化为加权网络图，问题就转化为在给定的加权网络图中，寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小。
1701009463
1701009464
1701009465
1701009466
1701009467
图8-1 乡镇、村的公路网
1701009468
1701009469
在加权图G中求最佳巡视路线问题是“NP—完全问题”，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下。
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
此问题包含两方面：第一，对顶点分组；第二，在每组中求最佳巡视回路，即为单个巡视员的最佳巡视回路问题。