1701009550
表8-2 重新分组后的近似最优解（单位：km）
1701009551
1701009552
1701009553
编号 路线 路线长度 路线总长度 I O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O 191.1 599.8 II O-2-5-6-7-E-8-E-9-F-10-F-12-H-14-13-G-11-J-19-L-6-5-2-O 216.4 III O-R-29-Q-30-32-31-33-35-34-A-1-B-C-3-D-4-D-3-2-O 192.3 由表8-2可知，因该分组的均衡度，所以这种分法的均衡性较好。
1701009554
1701009555
【问题】当巡视人员在各乡（镇）、村的停留时间一定，汽车的行驶速度一定，要在24h内完成巡视，至少要分几组及最佳的巡视路线。
1701009556
1701009557
【分析】
1701009558
1701009559
由于T=2h，t=1h，V=35km/h，需访问的乡镇共有17个，村共有35个。
1701009560
1701009561
1701009562
计算出在乡（镇）及村的总停留时间为17×2+35=69h，要在24h内完成巡回，若不考虑行走时间，有（i为分的组数），得i最小为4，故至少要分4组。
1701009563
1701009564
1701009565
1701009566
1701009567
由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡的分组，当分4组时各组停留时间大约为，则每组分配在路途上的时间大约为24-17.25=6.75h。而前面讨论过，分3组时有个总路程599.8km的巡视路线，分4组时的总路程不会比599.8km大太多，不妨以599.8km来计算。路上时间约为，若平均分配给4个组，每个组约需，故分成4组是可能办到的。
1701009568
1701009569
现在尝试将顶点分为4组。
1701009570
1701009571
分组的原则：除遵从前面准则一、二、三外，还应遵从以下准则。
1701009572
1701009573
准则四：尽量使各组的停留时间相等。
1701009574
1701009575
用上述原则，将图8-2分为4组，同时计算各组的停留时间，然后用加权图G（V，E）的最佳巡视路线的近似算法算出各组的近似最佳巡视员巡回，得出路线长度及行走时间，从而得出完成巡视的近似最佳时间。用加权图G（V，E）的最佳巡视路线的近似算法计算时，初始圈的输入与分3组时同样处理。
1701009576
1701009577
这4组的近似最优解如表8-3所示。
1701009578
1701009579
表8-3 重新分组的巡视路线（路程单位：km；时间单位：h）
1701009580
1701009581
1701009582
1701009583
1701009584
注：表8-3中加粗并为红色字体的表示前面经过并停留过，此次只经过不需停留；加框的表示此点只经过不停留。
1701009585
1701009586
1701009587
该分组实际均衡度。
1701009588
1701009589
可以看出，表8-3分组的均衡度很好，且完全满足24h完成巡视的要求。
1701009590
1701009591
1701009592
1701009593
1701009594
我和数学有约：趣味数学及算法解析 [:1701004256]
1701009595
我和数学有约：趣味数学及算法解析 8.2 盲人下山
1701009596
1701009597
【问题】何谓“盲人下山”？
1701009598
1701009599
【分析】