1701009431
我和数学有约：趣味数学及算法解析 [:1701004254]
1701009432
我和数学有约：趣味数学及算法解析 第8章 最优路径的选择
1701009433
1701009434
人生十字路口，面对抉择，是不是很难？是不是感觉不知道选择哪条路径才是适合自己的？本章通过最优路径分析，让你在灾情面前、下山路线规划前及旅行出发前有一个更加合理的选择。本章立足于生活实际，采用数形结合的方法，将你的抉择淋漓尽致的表现出来，下面开始我们的行程。
1701009435
1701009436
1701009437
1701009438
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