1701009439
我和数学有约：趣味数学及算法解析 [:1701004255]
1701009440
我和数学有约：趣味数学及算法解析 8.1 最佳灾情巡视路线
1701009441
1701009442
今年夏天某县遭受水灾，为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线是从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
1701009443
1701009444
【问题】若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线。
1701009445
1701009446
【分析】
1701009447
1701009448
假定巡视人员在各乡（镇）停留时间T=2h，在各村停留时间t=1h，汽车行驶速度V=35km/h，要在24h内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线。
1701009449
1701009450
乡镇、村的公路网示意图如图8-1所示。
1701009451
1701009452
首先对于该问题的求解，我们做出如下假设。
1701009453
1701009454
（1）汽车在路上的速度总是一定的，不会出现抛锚等现象；
1701009455
1701009456
（2）巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；
1701009457
1701009458
（3）每个小组的汽车行驶速度完全一样；
1701009459
1701009460
（4）分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路外）。
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