灾情巡视路线的数学模型12组标准

最优灾情巡视路线

摘要

本文解决的是灾情巡视路线的最佳安排问题，我们将其转化为多个推销员回路问题，并针对灾情巡视的不同要求，用哈密顿法求出了各情况下的近似最优解。

针对问题一：我们采用Kruskal法求出最小生成树，然后以最小生成树为依据将该县分为三个区域，分别对应三组巡视人员。然后利用哈密顿法求解出各组的巡视路程分别为197.6km、196.8km、206.8km，总路程为601.2km。最后用本文中自定义的均衡度来衡量分组的均衡性，路程均衡度为34%。此结果下的总路程相对较短，而均衡度偏高。如果要优先考虑均衡度，在最小生成树法求解发改进的基础上得到：194.0km、205.3km、206.8km，总路程为606.1km，路程均衡度为6.2%。

针对问题二： 针对问题三： 针对问题四：

关键字

1问题重述

下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。

问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。

2问题假设与符号说明

2.1问题假设

假设一：假设在巡视过程中不考虑天气、汽车故障等因素的影响。

假设二：假设路线上的公路没有被洪水冲断，可以供巡视工作正常使用。 假设三：假设在巡视过程中，经过邻县乡（镇）、村时，不做任何停留。 假设四：巡视人员上下车的时间及汽车加油时间忽略不计。 假设五：假设汽车在行驶途中车速不变且满足速度要求。

假设五：当巡视比较偏僻的乡村时，汽车从县政府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。

2.2符号说明 G（V,E） 赋权连通图； Gi赋权连通图的第i个子图(i Li 1,2,，k) 子图Gi中的最佳回路； 最佳回路Li的各边权值之和 第i个乡、村到第CiWijXij 53) j个乡、村的距离(i，j1,2,，某组从城市i到城市j时为1，无巡视组视为0 表示各乡（镇）停留时间 表示各村停留时间 eiej

3问题分析

本题给出了某县的道路交通网络图，要求的是在不同条件下，求解灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题，和旅行推销员问题类似。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图G(V,E)，且OV。两村之间的公路长度即为无向图的边权w(e)。寻找最佳巡视路线，即在图G(V,E)中找到一条包含O点的回路，它至少经过所有的顶点一次，且使得总路程或总时间最短。

对于问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图G(V,E)分为三个连通的子图Gi，且每个子图都与O点相连，然后在每个子图中寻找到一条含O点的最佳回路。针对三组巡视成员，需对该县分为三个区域。我们采用Kruskal算法通过MATLAB编程求出G图的最小树形图，然后将树形图分成三个区域，最后，采用哈密顿回路法求解每个子图内的最佳巡视路线。

对于问题二：在问题一的基础上，问题二增加了巡视人员在各乡（镇）、村停留时间以及汽车途中行驶时间，并要求在24小时内完成巡视，求最佳分组和最佳巡视路线使各组的时间均衡性较好。通过分析可得要使巡视人员在24小时内完成巡视，则巡视人员至少分四组，然后根据最小树形图，将整个区域分成四个区域，利用最佳哈密顿回路法，求解每个子图的最佳巡视路线和最短巡视时间。最后利用定义的均衡度公式求出时间均衡度，根据求出的均衡度判断各组是否均衡，若均衡度较大，说明分组不够均衡，需要继续改进直至时间均衡度在允许的范围内。

对于问题三：此问题就是要求如果有足够多的巡视人员，怎样确定最佳路线使完成巡视的时间最短。实际上，完成巡视的时间受到巡视最远乡（镇）、村路途时间和在乡（镇）、村停留时间的制约。通过分析可以求出巡视H镇花费的时间最长，为6.43小时。由此可知，即使巡视人员再多，分组再细，完成巡视至少需要6.43小时。于是我们制订了两种分组巡视原则：对图中偏西且距县政府较远的乡（镇）、村，巡视车开往最远巡视乡（镇）、村，并在途经乡村放下巡视员，到达最远乡镇后等待，然后按原路返回并且依次接回巡视员；对图中偏东且距县政府较近的乡（镇）、村，制定安全巡视原则，巡视车从县政府出发，巡视一圈并在途经乡村放下巡视员，车不停留继续巡视第二圈并在途中接回巡视员。然后根据分组原则，计算得出各组巡视时间。

对于问题四：要尽快完成巡视，就得要求各组完成巡视的时间尽可能相等，因为总的完成巡视的时间按最长巡视时间计算。显然在分组不变的情况下，无论T,t,V怎么改变，对每组的最佳巡视路线是没有影响的，但可能会影响各组间的均衡，因此此问题实际上是讨论T,t,V对分组的影响，即不破坏原来分组均衡性的条件下，T,t,V的最大变化范围。讨论不影响分组均衡时，定量的得出其他变量所允许的最大变化范围。最后根据得出的结论对分三组的实例进行讨论并分析结果。

4数据的分析与处理

4.1均衡度处理

本文定义均衡度公式为maxCiminCiCi1in，其中n表示分组数，i1,2...,n。

i/nCi表示各分组的路程或时间的权值，用来衡量分组的均衡性。设定0为最大

允许均衡度，显然01，越小，说明分组的均衡度越好。确定一个0后，

以下各模型的均衡度0，则模型精度良好，否则继续改进。

4.2最小树成法

因为最小树成中能包含图G中所有的顶点E，而且最小树的边权是相邻两顶点间的距离，它描述了顶点之间的相近程度，故可以采用最小生成树进行分组。本模型的主要思想是：首先采用Kruskal算法得到G图的最小生成树，然后基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。

利用下述Kruskal算法可以在赋权图求出最优树。 （1）选取边e1，使得w(e1)最小；

（2）设e1,e2,,ei已经选取，则在E{e1,e2,,ei}中选取边ei1使得： （ⅰ）G[{e1,e2,,ei,ei1}]不含圈；（ⅱ）w(ei1)尽可能小； （3）当第2步无法实施时停止。

根据Kraskal算法进行编程求解（具体程序见附录1），于是我们得到图G的最小生成树如图1。

图1

5问题一的解答

5.1模型一的准备 5.1.1确立最佳分组

现要分三组巡视，则需要把图G分成三个子图Gi(i1,2,3)，在每个子图Gi中寻找最佳回路Li(i1,2,3)。现对已得到的最小生成树进行分解，以获得三个子图Gi并使得分解结果尽量均衡。由于在最小生成树上，边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此，各个子图的顶点数应尽量接近17个，且遵循以下分解原则：

(Ⅰ)分解点为O点或尽可能地接近O点；（Ⅱ）分解所得的三个子图Gi的顶点数尽可能地接近17个；（Ⅲ）尽量是分解所得的子图是连通图；（Ⅳ）尽量使子图Gi与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路。

依据以上分解原则得到的分解结果如图2。

图2

然后，采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈，包含图G的每个顶点的圈称为哈

密顿圈。于是问题就可以转化为：现已知三个子图内乡、村与乡、村之间的距离，从县政府O出发，经过子图内的所有乡、村，最后又回到点O。 5.2模型一的建立 5.2.1确定目标函数

根据以上的分析确立了每个巡视组的巡视区域，分析出这是3个售货员寻求最佳旅行回路的问题。把县、乡、村所在地看作节点，根据路线图可以构造一个赋权网络图G,其中 （N,E,W）N0,1,2...,52,E(i,j)i,jN,Ww(i,j)i,jN

 根据图论中的结论，最佳售货员回路问题可转化为最佳汉密尔顿(hamilton)回路的问题。在图G的基础上构建三个子图Gi，于是在G中寻求最佳回路的问题即在Gi中寻找最佳(hamilton)回路的问题，于是决策变量定义为:

有巡视组从城市i到城市j1 ，xij

没有组巡视0 ，nn其线性（整数）规划模型目标函数为：minFwijxij。

i1j15.2.2确定约束条件

n目标函数给出了哈密顿圈的总长度，并使其最小。约束式xij1保证只

i1n能到达每个城市一次，约束式xij1保证只能离开一个城市一次，约束式

j1ijnxijn1( i ,j为自定义变量)是表述问题的关键，它确保：（1）由解得到的任何圈一定包含城市1（即县镇府点O）；（2）包含全部城市的圈是可行的。于是，约束条件概括为：

nxij1 ， j=1,2,,ni1nxij1 ， i=1,2,,nj1 ij, i,j=2,3,s.tijnxijn1 ，x0或1 ， ij, i,j=1,2,,n ijj0 ， j=1,2,,n n53,n

5.3综上所述，可得问题一的模型

目标函数：

nnminFwijxij

i1j1约束条件：

nxij1 ， j=1,2,i1,nnx1 ， i=1,2,,nj1ij ij, i,j=2,3,s.tijnxijn1 ，x0或1 ， ij, i,j=1,2,,n ijj0 ， j=1,2,,n n=53,n

5.4问题一的求解

按照上述思想写出相应程序（程序见附录二）求解得到三组巡视路线图见 表2： 组号 巡视路线 路线长度 总路线 1 O1B3435323133AR29Q3028272423N26PO 197.6 601.2 2 OM2521K221716I151413J1819L20O 196.8 3 O2567910F12HG11E84D3CO 206.8 模型的巡视路线图如下：

5.5问题一的结果分析

从模型一的结果可的清楚的看到三种不同的巡视路线，路程均衡度为

14.45%5%可知路程的均衡性较好，并且每一组所需要考察的乡（村）几乎相等，即每个组掌握各乡（村）情况较为均衡，符合实际生活中分派任务的情况，因此，方案三是非常合理的。

6问题二的解答

6.1模型二的准备

此问添加了巡视组在各乡（镇）停留的时间T2小时，在各村停留的时间t1小时以及汽车的行驶速度v35公里／小时的条件后，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。此时需访问的乡（镇）共有17个，村共有35个，于是可以计算出巡视人员在乡（镇）及村停留的总时间为1723569小时。此外，从问题一的结果中可知，巡视的总路程至少为500公里，则汽车行驶所需的时间和将超过14小时。由此可知，各组巡视所需的总

8324时间之和超过83小时，要想在24小时内完成巡视则应满足：i (i为分的组数)。得i最小为4，故至少要分4组。

现在尝试将顶点分成4组。分组的原则应建立在最小生成树的分解原则之上，则分组应遵循以下原则：

(Ⅰ)分解点为O点或尽可能地接近O点；（Ⅱ）分解所得的4个子图的顶点数尽可能地接近14个；（Ⅲ）尽量是分解所得的子图是连通图；（Ⅳ）尽量使子图Gi与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路；（v）尽量使各组的巡视时间相接近。

依据以上分解原则得到的分解结果如图4。

采用上述原则将G图分为4个子图，并运用哈密顿回路法找出各个组的最佳巡视路线。然后，计算出各组最佳巡视路线的总长度及汽车行驶所需时间，同时算出各组的停留时间,从而得到各组完成巡视的最佳时间。

6.2模型二的建立 6.2.1确定目标函数

由题中所给出的问题条件，分析出这是4个售货员寻求最佳旅行回路的问题。把县、乡、村所在地看作节点，根据路线图可以构造一个赋权网络图

根据图论中的结论，最佳售货员回路问题可转化为最佳汉密尔顿(Hamilton)GG回路的问题。在图G的基础上构建4个子图i，于是在G中寻求最佳回路的问题即在i中寻找最佳(Hamilton)回路的问题，于是决策变量定义为:

G[N,E,W],其中

N0,1,2...52,E(i,j)i,jN,Dd(i,j)i,jNxij1 ， 选择从城市i到城市j;  否则0 ，minFdij*Xiji1i1in1n其线性（整数）规划模型目标函数为：

5.2.2确定约束条件

目标函数给出了哈密顿圈的总时间长度，并使其最小。约束式

xi1inij1保

证只能到达每个城市一次，约束式式ixj1nij1保证只能离开一个城市一次，约束

jnxijn1( i ,j为自定义变量)是表述问题的关键，它确保：

（1）由解得到的任何圈一定包含城市1（即县镇府点O）；（2）包含全部城市的

圈是可行的。于是，约束条件概括为：

n j=1,2,,nxij1 ，i1n i=1,2,,nxij1 ，j1ijnxijn1 ， ij, i,j=2,3,,n  s.txij0或1 ， ij, i,j=1,2,,n  j=1,2,,n j0 ，SjSjT*Njt*Mj24,j1,2,3,4Vn535.3综上所述，得问题二的模型

目标函数：

minFdij*Xiji1i1in1n约束条件：

n j=1,2,,nxij1 ，i1n i=1,2,,nxij1 ，j1 s.tnxn1 ， ij, i,j=2,3,,n jijixij0或1 ， ij, i,j=1,2,,n  j=1,2,,n j0 ，n535.4问题二的求解

6问题三的解答

6.1模型三的建立

此问题就是要求如果有足够多的巡视人员，怎样确定最佳路线使完成巡视的时间最短。实际上，完成巡视的时间受到巡视最远乡（镇）、村路途时间和在乡（镇）、村停留时间的制约，由floyd算法可得到各点到O点最短距离的完全生成图.

由图上可求得距离O点最远的（乡镇）、村节点，分别为H点和14节点。考

虑在乡村停留时间，

Time[H]=77.5*2/35+2=6.43（h） Time[15]=69.6*2/35+1=4.98(h)

所以在所有节点中，巡视H镇所花费时间最大，由此可知，即使巡视人员再多，分组再细，完成巡视至少需要6.43小时。基于此，此问就可以转化为求在6.43小时内完成巡视的最少分组数和最佳巡视路线，为达到以上目标，我们制定了以下分组巡视原则：

1、对图中偏西且距县政府较远的乡（镇）、村：

（1）在6.4小时内，每组巡视人员尽可能走足够多的乡（镇）、村。

（2）在巡视时，尽量按出发点到该次巡视终点最短路径的路线巡视，但在不超过6.4小时的原则下，为了能够途经更多的点，我们可以不走最短路线。 （3）巡视车从县政府出发，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视人员上、下车的时间）继续开往下个站点，直到到达最远点，车停下等待；然后按原路返回，依次到达每点接回巡视人员，直至出发点。

2、由于第一种分组原则下，在最远点必须要花1或者2个小时的停留时间，针对这一浪费时间的缺点，对图中偏东且距县政府较近的乡、村，我们改进一种按圈巡视的方法，原则如下：

（1）每组巡视人员巡视路线构成一个圈，且巡视两圈。 （2）第一圈巡视时，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视人员上、下车的时间）继续开往下个站点，直至出发点，仍不停留继续第二圈巡视，到达每点依次接回巡视人员，直至回到出发点，结束。 （3）在遵循不超过6.4小时原则下，按圈巡视时，圈总路线不能过长，不超过112公里；总路线也不能过短，避免车停留等待而浪费时间。

6.2模型三的求解

依据以上分组原则，我们在6.4小时内完成巡视，总共分成了7组，前5组遵循的第一 种分组原则，后2组依据的第二种按圈分组原则。于是得到各组的巡视路线和停留点时间如下表:

组号 巡视路线 时间 1 O2567E9F12H14H12F9E7652O 6.43 2 OM252021K18L15L18K212025MO 5.87 3 O256L19J13G11G13J19L652O 6.15 4 O23D48E9F10F9E84D32O 6.38 5 OP282726N242322171617222324N262728PO 6.37 6 O12R3133A34BC1O12R3133A34BC1O 5.38 7 OR29Q30323534A1OR29Q30323534A1O 5.48 由上表可以看出各个组的巡视时间均小于6.43小时，符合题意，此外，计算得到该分组的时间均衡度公式为：

hhmin=maxi7hii1

此时，计算得到均衡度：17.5%。在此基础上，我们可以得到有时间约束的最佳巡视路线如图4。

7问题四的解答

7.1模型四的建立

巡视组数已定，要求尽快完成巡视，讨论T,t,和V的改变对最佳巡视路线的影响。要求尽快完成巡视，就的要求每组完成巡视时间尽量均衡，因为总的完成巡视时间按最长的完成巡视时间计算。现在讨论在均衡度允许的范围内已分成n组后，改变T,t,和V对最佳巡视路线的影响。显然在分许不变的情况下，无论T,t,和V如何改变，对每组内的最佳巡视路线是没有影响的，但可能会影响个组间的均衡性。因此该问题实际上讨论T,t,和V对于分组的影响，即在不破坏原来分组均衡的条件下，T,t,和V允许的最大变化范围。 在分组为n的情况下，设

Si：表示第i组的最佳推销员贿赂路线总长度； Xi：表示第i组所要停留的乡镇数目； Yi：表示第i组所要停留的村的数目；

其中：i1,2,3...,n。显然，当XiXj,YiYj,SiSj;i,j1,2,3...,n时，即每组的乡镇树、村数、最佳选会的长度均相等，因而分组绝对均衡时，T,t,和V的最大允许变化范围的讨论：

对于任意一个组i，其完成巡视的时间

SiTiXiTYt,i1,2,3...,n iV设均衡分组的最大允许时间均衡度为，即 TiTji,j1,2,3...,n maxTi

则有：TiTj*maxTi

记*maxTi，则表示均衡返租所允许的最大时间误差，则

T(XiXj)t(YiYj)由（1）式我们得到

SiSjV （1）

T(XiXj)t(YiYj)SiSjV （2）

由式（2）可得

1.当XiXj0时，要保持云均衡分组不变,T必须满足的条件为：

SiSjSiSj(YY)t(YY)tijijVVmaxTminXiXj0XiXj0XXXXijij（3）

2当YiYj0时，要保持原均衡分组不变，t必须满足的条件为： SiSjSiSj(XiXj)T(XiXj)TVVmaxtminYiYj0YiYj0YiYjYiYj（4）

3当SiSj0时，由（2）式得 V（1）当T(XiXj)t(YiYj)时，有 T(XiXj)t(YiYj)SiSjT(XiXj)t(YiYj)



SiSjVmax （5） SiSj0(XX)T(YY)tijij（2）当T(XiXj)t(YiYj)时，有

SiSjVmin （6） SiSj0(XX)T(YY)tijijSiSjSiSjmaxVmin SiSj0(XX)T(YY)tSiSj0(XX)T(YY)tijijijij由（3）-(6)式，当T,t,和V三个变量中任意两个变量无论如何如何变化，都可计算出为保持均衡性分组不变，三个变量所允许的最大变化范围。 （二）分三组的实例讨论

先对分三组的情况进行分步讨论，对问题一中所得的三个分组，若考虑停留时间和行驶时间且取TT02小时，tt1小时，VV35公里/小时，结果如

00表5：

（三）对实例结果的分析

tt01上述实例的均衡分组有一个特点，各组的停留时间相等，即取TT02，

小时，VV035公里/小时，在表5的分组中

(XiXj)T0(YiYj)t00,i,j1,2,3 （7）

定义4各组的停留时间相等的均衡分组成为停留时间相等的均衡分组，由（7）式得

YYj T0i*t0,XiXj0,i,j1,2,3 （8）

XiXj先讨论对停留时间相等的均衡分组，T,t,V的变化规律，对停留时间相等的均衡分组，分组的实际时间误差：

SiSj0max(XiXj)*T0(YiYj)t0 i,jV0SiSjSiSj max （9） i,jV0V0其中，i为使Si最大组的标号；j为最小的足的标号。

当T,t不变时，即TT0,tt0时，因(XiXj)T0(YiYj)t00，由（6）

式知道，要保持平衡分组，V的下界应为：

SiSjSiSjSiSjVmaxmax(i,j的含义不同) SS0SiSj0(XX)T(YY)tijijij(1)取0时，由（9）式得

SiSjVmaxV0

（1）取0时，由（9）式得

SiSjVminV0

故有以下定理

定理：当VV0,TT0,tt0时，对图进行停留时间相等的均衡分组后，设该分组的实际时间误差为0。

（1）若取最大允许时间误差0，当T,t不变时，要使该均衡分组保持不变，

V的下界V0即V只能增加不能减少

（2）若取最大允许时间误差0，当T,t不变时，要使该均衡分组保持不变，V的变化范围的下界小于V0

7模型的评价、改进与推广

7.1模型评价 优点

（1）本文对问题一二通过求最小生成树图，来进行分组，这样是问题简化，然后对结果进行微调，得到均匀性较好的分组路线，使文章思路清晰。

（2）本文定义了路程均衡度和时间均衡度，定量的刻画了时间的均衡性。 （3）在问题三的求解中，我们假定当巡视比较偏僻的乡村时，汽车从县镇府出

发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员，这样考虑可以避免车停留等待而浪费时间，提高巡视效率。

（4）从理论上定量的讨论了V,T,t的变化对均衡分组灵敏度的影响，得到了很好的结果。 缺点

（1）我们利用最有树分解方法对图分块，虽然有分块原则，但没有给出一个准确的原则定量的给出总路程最短同均衡性最好的关系。 7.2模型改进

⑴采用最小生成树求解最小回路，并采用Hmilton圈法求解各子图内的最佳回路，虽然分组的均衡度比较理想，但求的不是全局最优解。

7.3模型推广

该问题可看作多个旅行商问题，可以应用的范围较广，只要是寻求最佳哈密顿圈，该模型均可以作为参考。

8参考文献

[1] 宋来忠，王志明,数学建模与实验,北京：科学出版社,2005。 [2] 刘承平，数学建模方法,北京：高等教育出版社，2001。

[3] 冯杰 黄力伟，数学建模原理与案例，北京：科学出版社，2007。 [4] 田家国,数学的实践与认识，北京：科学出版社，1999.1。

9附录

附录一：Kruskal最小树成法程序

clear all

%图论最小生成树Kruskal避圈算法 %w为邻接矩阵 w=[

0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.3 5.9 11.2 inf inf inf inf inf inf inf inf inf inf inf 6 inf inf inf ;

inf 0 4.8 inf 8.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.2 inf inf inf ;

inf 4.8 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.8 8.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf 0 inf inf inf 20.4 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12.7 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf 8.3 inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.3 inf inf inf inf inf inf inf inf 11.4 inf inf inf inf inf ;

inf inf inf inf 9.7 0 7.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.8 9.5 inf inf inf inf inf ;

inf inf inf inf inf 7.3 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 15.1 7.2 inf inf inf inf inf inf 14.5 inf inf inf inf inf inf ;

inf inf inf 20.4 inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8 inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.8 5.6 inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.8 inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 14.2 inf 6.8 inf inf 13.2 inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12.2 7.8 10.2 inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf 0 8.6 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.8 inf 16.4 9.8 inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf 8.6 0 15 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 9.9 inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf 15 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.8 inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 6.8 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.8 inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 6.8 0 inf inf inf inf 6.7 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 9.8 inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.2 8.2 9.2 inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 9.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.1 inf 7.2 inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 9.3 0 7.9 inf inf inf 6.5 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 5.5 inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.9 0 inf 9.1 inf 7.8 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 4.1 inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 6.7 inf inf inf inf 0 10 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.1 inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 9.1 10 0 8.9 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.9 inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.9 0 inf inf 18.8 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 13.2 inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 6.5 7.8 inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12 8.8 inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 7.8 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.5 inf 10.5 inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 18.8 inf 7.8 0 7.9 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.9 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12.1 8.3 inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 15.2 7.2 7.8 ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf 10.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.7 inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 8.1 7.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 9.2 ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.1 0 19 inf 14.9 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.3 7.3 19 0 inf inf 7.4 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 8.2 11.5 17.8 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 14.9 inf 8.2 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

10.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.4 11.5 inf 0 inf inf

];

n=53;%有53个点 k=1;

for i=1:n-1 for j=i+1:n if w(i,j)~=inf

x(1,k)=w(i,j);%记录边 x(2,k)=i;%记录起点 x(3,k)=j;%记录终点 k=k+1;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.8 ;

5.9 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 17.8 inf inf 0 11 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

11.2 inf 7.8 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11 0 inf inf inf inf inf inf inf inf inf inf inf 11.5 inf inf inf ;

inf inf 8.2 12.7 11.3 inf 15.1 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf 7.2 8 7.8 inf 14.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf 5.6 10.8 inf 12.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf 6.8 7.8 8.8 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf 10.2 inf 9.9 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf 16.4 inf inf 11.8 inf 8.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf 13.2 inf 9.8 inf inf inf inf 8.2 8.1 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 9.8 9.2 inf inf 4.1 10.1 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf ;

inf inf inf inf inf 11.8 14.5 inf inf inf inf inf inf inf 8.8 inf inf inf 7.2 5.5 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf ;

inf inf inf inf 11.4 9.5 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 14.2 19.8 inf inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.9 13.2 8.8 10.5 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 14.2 0 inf inf inf inf ;

6 8.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.5 inf inf inf inf inf inf inf inf inf 19.8 inf 0 10.1 inf 12.8 ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.5 inf 12.1 15.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.1 0 inf inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.3 7.2 7.7 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf ;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.8 inf 9.2 inf inf inf inf 8.8 inf inf inf inf inf inf inf inf inf inf inf inf inf 12.8 inf inf 0 ;

end end end

k=k-1;%统计边数 k为边数

%步骤一

%冒泡法给边的大小排序 for i=1:k for j=i+1:k

if x(1,i)>x(1,j)

a=x(1,i);x(1,i)=x(1,j);x(1,j)=a; a=x(2,i);x(2,i)=x(2,j);x(2,j)=a; a=x(3,i);x(3,i)=x(3,j);x(3,j)=a; end end end

%给各点标号赋初值 for i=1:n l(i)=i; end

%初始时选e1加入集合E

E(1,1)=x(1,1); %E矩阵的第一行记录最小生成树的边长 E(2,1)=x(2,1); %E矩阵的第二行记录边的起点 E(3,1)=x(3,1); %E矩阵的第三行记录边的终点 a=min([l(E(2,1)),l(E(3,1))]); l(E(2,1))=a;l(E(3,1))=a; b=1;%记录E中边数

for i=2:k

%步骤四

if b==n-1 %如果树中边数达到n-1 break %算法终止 end

%步骤二

if l(x(2,i))~=l(x(3,i)) %如果两顶点标号不同 b=b+1; %将这条边加入E E(1,b)=x(1,i); E(2,b)=x(2,i); E(3,b)=x(3,i);

%步骤三

for j=1:n %对于所有顶点

if l(j)==max([l(E(2,b)),l(E(3,b))])%如果该顶点的标号,等于=,新加入边中的顶点标号较大的值

l(j)=min([l(E(2,b)),l(E(3,b))]);%将其改为较小的那一个以避圈 end end end end E

附录二：问题一的求解程序 1、第一组巡视路线程序

clc,clear a=[

0 45.0000 50.3000 26.6000 34.4000 28.2000 26.6000 28.0000 25.0000 33.1000 17.7000 21.8000 30.0000 10.3000 5.9000 37.1000 6.0000 16.1000 33.8000 18.8000;

45.0000 0 8.9000 18.4000 26.2000 34.1000 44.1000 50.1000 61.0000 69.1000 60.4000 66.8000 75.0000 55.3000 50.9000 7.9000 39.0000 28.9000 42.4000 51.8000;

50.3000 8.9000 0 23.7000 18.8000 26.7000 42.2000 42.7000 59.2000 67.3000 53.0000 70.3000 78.5000 58.8000 56.2000 13.2000 44.3000 34.2000 35.0000 50.0000;

26.6000 18.4000 23.7000 0 7.8000 15.7000 25.7000 31.7000 42.6000 50.7000 42.0000 48.4000 56.6000 36.9000 32.5000 10.5000 20.6000 10.5000 24.0000 33.4000;

34.4000 26.2000 18.8000 7.8000 0 7.9000 23.4000 23.9000 40.4000 48.5000 34.2000 51.5000 59.7000 40.0000 40.3000 18.3000 28.4000 18.3000 16.2000 31.2000;

28.2000 34.1000 26.7000 15.7000 7.9000 0 15.5000 16.0000 32.5000 40.6000 26.3000 43.6000 51.8000 32.1000 34.1000 26.2000 22.2000 12.1000 8.3000 23.3000;

26.6000 44.1000 42.2000 25.7000 23.4000 15.5000 0 14.9000 17.0000 25.1000 24.0000 28.1000 36.3000 16.6000 32.5000 36.2000 20.6000 15.2000 7.2000 7.8000;

28.0000 50.1000 42.7000 31.7000 23.9000 16.0000 14.9000 0 17.6000 25.7000 10.3000 29.2000 37.4000 17.7000 33.9000 42.2000 34.0000 28.1000 7.7000 22.7000;

25.0000 61.0000 59.2000 42.6000 40.4000 32.5000 17.0000 17.6000 0 8.1000 7.3000 26.2000 23.0000 14.7000 30.9000 53.1000 22.0000 32.1000 24.2000

9.2000;

33.1000 69.1000 67.3000 50.7000 48.5000 40.6000 25.1000 25.7000 8.1000 0 15.4000 23.1000 14.9000 22.8000 39.0000 61.2000 30.1000 40.2000 32.3000 17.3000;

17.7000 60.4000 53.0000 42.0000 34.2000 26.3000 24.0000 10.3000 7.3000 15.4000 0 18.9000 27.1000 7.4000 23.6000 52.5000 23.7000 33.8000 18.0000 16.2000;

21.8000 66.8000 70.3000 48.4000 51.5000 43.6000 28.1000 29.2000 26.2000 23.1000 18.9000 0 8.2000 11.5000 17.8000 58.9000 27.8000 37.9000 35.3000 20.3000;

30.0000 75.0000 78.5000 56.6000 59.7000 51.8000 36.3000 37.4000 23.0000 14.9000 27.1000 8.2000 0 19.7000 26.0000 67.1000 36.0000 46.1000 43.5000 28.5000;

10.3000 55.3000 58.8000 36.9000 40.0000 32.1000 16.6000 17.7000 14.7000 22.8000 7.4000 11.5000 19.7000 0 16.2000 47.4000 16.3000 26.4000 23.8000 8.8000;

5.9000 50.9000 56.2000 32.5000 40.3000 34.1000 32.5000 33.9000 30.9000 39.0000 23.6000 17.8000 26.0000 16.2000 0 43.0000 11.9000 22.0000

39.7000 24.7000; 37.1000 7.9000 13.2000 10.5000 18.3000 26.2000 36.2000 42.2000 53.1000 61.2000 52.5000 58.9000 67.1000 47.4000 43.0000 0 31.1000 21.0000 34.5000 43.9000;

6.0000 39.0000 44.3000 20.6000 28.4000 22.2000 20.6000 34.0000 22.0000 30.1000 23.7000 27.8000 36.0000 16.3000 11.9000 31.1000 0 10.1000 27.8000 12.8000;

16.1000 28.9000 34.2000 10.5000 18.3000 12.1000 15.2000 28.1000 32.1000 40.2000 33.8000 37.9000

46.1000 26.4000 22.0000 21.0000 10.1000 0 20.4000 22.9000;

33.8000 42.4000 35.0000 24.0000 16.2000 8.3000 7.2000 7.7000 24.2000 32.3000 18.0000 35.3000 43.5000 23.8000 39.7000 34.5000 27.8000 20.4000 0 15.0000;

18.8000 51.8000 50.0000 33.4000 31.2000 23.3000

7.8000 22.7000 9.2000 17.3000 16.2000 20.3000 28.5000 8.8000 24.7000 43.9000 12.8000 22.9000 15.0000 0;

];

c1=[17 1 15 12 13 10 9 11 14 20 7 8 19 6 5 3 2 16 4 18 17]; L=length(c1); flag=1;

while flag>0 flag=0; for m=1:L-3

for n=m+2:L-1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1)) a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1;

c1(m+1:n)=c1(n:-1:m+1); end end end end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1)); end

circle=c1; sum=sum1;

<

c1=[17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 17];%改变初始圈，该算法的最后一个顶点不动 flag=1;

while flag>0 flag=0; for m=1:L-3

for n=m+2:L-1

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1;

c1(m+1:n)=c1(n:-1:m+1); end end end

end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1)); end

if sum1circle,sum

2、第二组巡视路线程序

clc,clear a=[

0 8.6000 23.6000 28.2000 35.0000 18.0000 17.9000 27.2000 31.3000 37.3000 33.7000 16.4000 9.8000 27.2000 25.1000 45.7000 65.5000

8.6000 0 15.0000 35.6000 42.4000 26.6000 26.5000 35.8000 39.9000 45.9000 42.3000 23.8000 18.4000 35.8000 33.7000 54.3000 74.1000

23.6000 15.0000 0 20.6000 27.4000 17.0000 33.3000 38.2000 30.3000 34.1000 38.1000 8.8000 25.2000 26.2000 40.5000 50.1000 69.9000

28.2000 35.6000 20.6000 0 6.8000 20.0000 36.3000 28.6000 20.7000 13.5000 28.5000 11.8000 28.2000 16.6000 34.1000 40.5000 60.3000

35.0000 42.4000 27.4000 6.8000 0 19.0000 31.1000 21.8000 13.9000 6.7000 21.7000 18.6000 27.2000 9.8000 27.3000 33.7000 53.5000

18.0000 26.6000 17.0000 20.0000 19.0000 0 16.3000 21.2000 13.3000 19.3000 21.1000 8.2000 8.2000 9.2000 23.5000 33.1000 52.9000

17.9000 26.5000 33.3000 36.3000 31.1000 16.3000 0 9.3000 17.2000 31.4000 15.8000 24.5000 8.1000 21.3000 7.2000 27.8000 47.6000

27.2000 35.8000 38.2000 28.6000 21.8000 21.2000 9.3000 0 7.9000 22.1000 6.5000 29.4000 17.4000 12.0000 5.5000 18.5000 38.3000

31.3000 39.9000 30.3000 20.7000 13.9000 13.3000 17.2000 7.9000 0 14.2000 7.8000 21.5000

];

21.5000 4.1000 13.4000 19.8000 39.6000

37.3000 45.9000 34.1000 13.5000 6.7000 19.3000 31.4000 22.1000 14.2000 0 22.0000 25.3000 27.5000 10.1000 27.6000 34.0000 53.8000

33.7000 42.3000 38.1000 28.5000 21.7000 21.1000 15.8000 6.5000 7.8000 22.0000 0 29.3000 23.9000 11.9000 12.0000 12.0000 31.8000

16.4000 23.8000 8.8000 11.8000 18.6000 8.2000 24.5000 29.4000 21.5000 25.3000 29.3000 0 16.4000 17.4000 31.7000 41.3000 61.1000

9.8000 18.4000 25.2000 28.2000 27.2000 8.2000 8.1000 17.4000 21.5000 27.5000 23.9000 16.4000 0 17.4000 15.3000 35.9000 55.7000

27.2000 35.8000 26.2000 16.6000 9.8000 9.2000 21.3000 12.0000 4.1000 10.1000 11.9000 17.4000 17.4000 0 17.5000 23.9000 43.7000

25.1000 33.7000 40.5000 34.1000 27.3000 23.5000 7.2000 5.5000 13.4000 27.6000 12.0000 31.7000 15.3000

17.5000 0 24.0000 43.8000 45.7000 54.3000 50.1000 40.5000 33.7000 33.1000 27.8000 18.5000 19.8000 34.0000 12.0000 41.3000 35.9000 23.9000 24.0000 0 19.8000

65.5000 74.1000 69.9000 60.3000 53.5000 52.9000 47.6000 38.3000 39.6000 53.8000 31.8000 61.1000 55.7000 43.7000 43.8000 19.8000 0

c1=[17 1 15 12 13 10 9 11 14 7 8 6 5 3 2 16 4 17]; L=length(c1); flag=1;

while flag>0 flag=0; for m=1:L-3

for n=m+2:L-1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1)) a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1;

c1(m+1:n)=c1(n:-1:m+1); end end end end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1)); end

circle=c1; sum=sum1;

<

c1=[17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17];%改变初始圈，该算法的最后一个顶点不动 flag=1;

while flag>0 flag=0; for m=1:L-3

for n=m+2:L-1

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1;

c1(m+1:n)=c1(n:-1:m+1); end end end end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1)); end

if sum1end

circle,sum

3第三组巡视路线程序

clc,clear a=[

0 4.8000 25.7000 8.3000 18.0000 25.3000 40.5000 40.3000 56.7000 46.7000 58.1000 12.6000 13.0000 32.5000 45.9000 53.5000 68.3000 8.2000

4.8000 0 20.9000 13.1000 22.8000 23.3000 38.5000 38.3000 54.7000 44.7000 56.1000 7.8000 8.2000 30.5000 43.9000 51.5000 66.3000 13.0000

25.7000 20.9000 0 24.0000 33.7000 27.8000 20.4000 36.2000 52.6000 42.6000 54.0000 28.7000 12.7000 28.4000 41.8000 49.4000 64.2000 33.9000

8.3000 13.1000 24.0000 0 9.7000 17.0000 32.2000 32.0000 48.4000 38.4000 49.8000 20.9000 11.3000 24.2000 37.6000 45.2000 60.0000 16.5000

18.0000 22.8000 33.7000 9.7000 0 7.3000 22.5000 22.3000 38.7000 28.7000 40.1000 30.6000 21.0000 14.5000 27.9000 35.5000 50.3000 26.2000

25.3000 23.3000 27.8000 17.0000 7.3000 0 15.2000 15.0000 31.4000 21.4000 32.8000 31.1000 15.1000 7.2000 20.6000 28.2000 43.0000 33.5000

46.7000 44.7000 42.6000 38.4000 28.7000 21.4000 22.2000 22.0000 37.6000 0 14.6000 52.5000 36.5000 14.2000 26.8000 6.8000 24.8000 54.9000

58.1000 56.1000 54.0000 49.8000 40.1000 32.8000 33.6000 17.8000 23.0000 14.6000 0 63.9000 47.9000 25.6000 12.2000 7.8000 10.2000 66.3000

12.6000 7.8000 28.7000 20.9000 30.6000 31.1000 46.3000 46.1000 62.5000 52.5000 63.9000 0 16.0000 38.3000 51.7000 59.3000 74.1000 11.5000

13.0000 8.2000 12.7000 11.3000 21.0000 15.1000 30.3000 30.1000 46.5000 36.5000 47.9000 16.0000 0 22.3000 35.7000 43.3000 58.1000 21.2000

32.5000 30.5000 28.4000 24.2000 14.5000 7.2000 8.0000 7.8000 24.2000 14.2000 25.6000 38.3000 22.3000 0 13.4000 21.0000 35.8000 40.7000

45.9000 43.9000 41.8000 37.6000 27.9000 20.6000 21.4000 5.6000 10.8000 26.8000 12.2000 51.7000 35.7000 13.4000 0 20.0000 22.4000 54.1000

40.5000 38.5000 20.4000 32.2000 22.5000 15.2000 53.5000 51.5000 49.4000 45.2000 35.5000 28.2000 0 15.8000 32.2000 22.2000 33.6000 46.3000 30.3000 8.0000 21.4000 29.0000 43.8000 48.7000

40.3000 38.3000 36.2000 32.0000 22.3000 15.0000 15.8000 0 16.4000 22.0000 17.8000 46.1000 30.1000 7.8000 5.6000 25.6000 28.0000 48.5000

56.7000 54.7000 52.6000 48.4000 38.7000 31.4000 32.2000 16.4000 0 37.6000 23.0000 62.5000 46.5000 24.2000 10.8000 30.8000 33.2000 64.9000

29.0000 25.6000 30.8000 6.8000 7.8000 59.3000 43.3000 21.0000 20.0000 0 18.0000 61.7000

68.3000 66.3000 64.2000 60.0000 50.3000 43.0000 43.8000 28.0000 33.2000 24.8000 10.2000 74.1000 58.1000 35.8000 22.4000 18.0000 0 76.5000

8.2000 13.0000 33.9000 16.5000 26.2000 33.5000 48.7000 48.5000 64.9000 54.9000 66.3000 11.5000 21.2000 40.7000 54.1000 61.7000 76.5000 0

];

c1=[17 1 15 12 13 10 9 11 14 7 8 6 5 3 2 16 4 18 17]; L=length(c1); flag=1;

while flag>0 flag=0; for m=1:L-3

for n=m+2:L-1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))

<

a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1;

c1(m+1:n)=c1(n:-1:m+1); end end end end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1)); end

circle=c1; sum=sum1;

c1=[17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17];%改变初始圈，该算法的最后一个顶点不动 flag=1;

while flag>0 flag=0; for m=1:L-3

for n=m+2:L-1

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1;

c1(m+1:n)=c1(n:-1:m+1); end end end end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1)); end

if sum1circle,sum

附录三：问题二的求解程序