电缆铺设问题.doc

电缆铺设问题
摘要
本文解决的是军营电缆铺设最优策略的图论问题。首先，根据题意分析12个营之间边的权值特点，然后，确定采用算法和标号算法解决问题，最后，自定义函数，建立以最小权值和为目标函数的最优路径问题。
对于问题一：假设各个营点为顶点，各营点间的路线为边，通过采用算法求得原图的最小生成树进而求出最短铺设路线。采用类比推理的思想，由易到难推出目标函数为最小权值和，用软件编程求解出最短电缆铺设长度为206千米。通过将结果图与原题图进行对比，可以判断出结果的合理性。下表为问题一中电缆铺设具体路线：（单位：千米）

边
1-3
1-11
1-8
8-4
8-2
2-12

12-9
12-6
12-5
5-10
10-7
总
长
35
45
18
15
5
23
15
14
17
16
13
216

对于问题二：同问题一，将各个营点假设为顶点，各营点间的路线假设为边，目标函数依然为最小权值和。通过标号算法运用软件编程求解出在问题二条件下的最短电缆铺设长度为308千米。通过将结果图与原题图进行对比，可以判断出结果的合理性。下表为问题二中电缆铺设具体路线：（单位：千米）

边
1-3
1-11
1-4
1-5
1-7
1-8
4-9
7-10
长
35
45
20
27
29
18
26
13
边
10-6
8-2
2-12
12-9
12-6
12-5
8-2
10-7
长
21
5
23
15
14
17
5
13
总长
308

由于各边所选用电缆线的截面以及线损（权值）在规划方案确定之前是无法知道的，所以在模型改进中提出算法的改进。本模型还适用于单向最短路线问题。

关键词： 类比推理 无向图 算法 算法 最小生成树
19

1. 问题重述
1.1问题背景
在21世纪的今天，信息交流和物质交流日益频繁，交流的路线也日趋复杂化。怎样从复杂的交通网中找出最优的交通路径，方便人们的交流，也成为人们所关心的问题。最优路径的选择，作为图与网络技术研究中的一个经典问题一直在出门旅游、重要机构的选址、工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用,对该问题求解的算法设计有着重要的理论和应用价值.在错综复杂的网络中找出最优路线显得至关重要。

1.2问题所给信息
某次军事演习12个大本营之间的电缆铺设构成的通讯网络图如下，从图中可以清晰地看出各大本营之间的地理位置分布情况，也可以清楚地读出各大本营之间的距离（单位：千米）。

.
图一：12个大本营之间的路线及距离（单位：千米）
1.3问题的提出
问题一：要保证任意两营之间都有线缆连结，问至少要铺设多长的线缆？
问题二：为了保证在其他任意三个营节点遭到破坏通讯中断时，1营和12营仍然可以通讯，求此种情况下的最小铺设长度和铺设方法？

2. 模型假设
假设一：只考虑距离，不考虑其它因素对题目所求最小距离的影响；
假设二：每两个营之间铺设的电缆均为直线；
假设三：不考虑其它电缆的故障对所求线路电缆的影响；
假设四：不考虑各营的大小和体积，各营可视为一个个点，点与点之间的线路可以视为无向图的直线边。

3.符号说明
符号
符号意义

无向图中各点所对应的边

无向图中各点所对应的边的权值

无向图中节点的点集

无向图中任意两点的距离

无向图中节点

无向图中任意两点的连接状态

3. 数据分析
根据原题所给图一，做出如下权值表：
表一：各营点间边的权值

1
2
3
4
5
6
7
8
9
10
11
12
1
0
0
35
20
27
0
29
18
0
0
45
0
2

0
0
0
40
0
0
5
0
0
0
23
3

0
0
0
0
0
0
0
0
0
0
4

0
0
0
0
15
26
0
61
0
5

0
46
29
38
0
16
0
17
6

0
0
0
0
21
0
14
7

0
0
0
13
0
0
8

0
0
0
0
0
9

0
0
0
15
10

0
0
0
11

0
0
12

0

题目给出了12个营及连接各营的20条赋权值的边，将各营点视作点，将各边视为直线。各营点周围边的权重大小不一，例如6营点，最大权重为46，最小为14。题中权重最小为5，最大为61。其中1营点与5营点连接的边数最多，均为6条，在这两点周围边的取舍尤为关键。3营点只与1营点相关，故不予考虑，
4. 问题分析
本文研究的是一个最优化路径问题。问题中给出了一个由12个营构成的复杂的电缆连接网络图。本文需要从复杂的连接网络图中选出最短的电缆连接路线。
题目所给电缆连接网络图为无向图，故欲求在各种情况下的最短电缆铺设路径的长度，只需求各路径的权值总和的最小值即可。
针对问题一：要求保证任意两营之间都有线缆连结，求最短路径，故需用11条边连接这12个点，即求最小生成树。采用算法基于顶点来实现最小生成树。假设使用邻接矩阵来存储图，在算法实现的过程中，需要以下两类信息
（1）集合T1内各顶点到集合T2中各顶点的权值最小的边的权值（其中T2集合是表示这些集合中的点已经是最小生成树中的点了）；
（2）集合T1内各顶点距离集合T2最小的顶点。
据此，问题一中最小生树的形成分析如下图所示：

图二：问题一分析流程图
针对问题二：要求保证在其他任意三个营节点遭到破坏通讯中断时，1营和12营仍然可以通讯，故1营与12营之间有4条互不重合的铺设路线。又根据数据分析得与1营点连接的6个营点中，3营点只与1营点连接，11营点与1营点和4营点连接，而4营点不予考虑，故7营点、5营点、8营点、4营点符合条件，应从这四个营点着手。
5. 模型的建立及求解
6.1模型一的建立及求解
6.1.1模型一的建立
一、目标函数的导出
先将各营和两两之间的直线距离抽象成点和线，构成一个无向图，对的每一条边，可赋以一个权值（本题中为各营之间的距离）连同它边上的权称为赋权图，图的生成子图称的生成树。
对于问题一，要求最小生成树各边的最小距离的和，只需使得对应的最小生成树的边的最小权值的和最小即可。
（一）当无向图中只有4个点时：
（1） 从中任选一个点，找出与 相连且权值最小的边，边的长度即所对的权值，记为：，边的另一端点记为。则与之间最小权值为：

其中：

（2）以为顶点重复（1）分别求出最小生成树各边的最小权值 。当时结束。此时所求的最小值的总和为：

（二）当无向图中有个点时：
依据（一）只有4个点的推理容易得出，当有更多点（个点的情况）的情况时的最小生成树各边最小权值的总和为：

二、约束条件的导出
根据题意，每个营点必须和任意另外一个营点连接，故个点不出现连通圈得出约束条件：

综上所述，问题一的优化模型为：

6.1.2模型一的求解
采用算法基于顶点来实现最小生成树，用软件编程求解这个图的最小生成树。其加权邻接矩阵如下:
表一：问题一模型求解矩阵（单位：千米）

1
2
3
4
5
6
7
8
9
10
11
12
1
0
0
35
0
0
0
0
18
0
0
45
0
2
0
0
0
0
0
0
0
5
0
0
0
23
3
35
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
15
0
0
0
0
5
0
0
0
0
0
0
0
0
0
16
0
17
6
0
0
0
0
0
0
0
0
0
0
0
14
7
0
0
0
0
0
0
0
0
0
13
0
0
8
18
5
0
15
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
15
10
0
0
0
0
16
0
13
0
0
0
0
0
11
45
0
0
0
0
0
0
0
0
0
0
0
12
0
23
0
0
17
14
0
0
15
0
0
0
图中显示1营点与3营点、8营点、11营点连接，2营点与8营点、12营点连接12营点与2营点、5营点、6营点、9营点连接。根据所得结果，画出如下最小生成树（即最优铺设电缆路线）：

图三：问题一最优铺设电缆路线（单位：千米）
通过求最小生成树各边权值的和，进而求得距离的最小值。
得最小值为：35+45+18+15+5+23+15+14+17+16+13=216（千米）。
6.1.3模型一结果分析
按照以上最优解，从1营到12营之间铺设电缆构成通讯网络，分别是1-3,1-11,1-8,8-4,8-2,2-12,12-9,12-6,12-5,5-10,10-7两两互相连通，构成了一个最小生成树，电缆总长度最小为216km,根据部分军营距离，通过与上文分析的对比可知，对问题一的分析合理。而prim算法正好解决了本题的问题。下面，将结果图与原题图进行对比：

图四：问题一答案与原图的对比
通过将结果图与原题图进行对比，可以判断结果合理。
6.2模型二的建立及求解
6.2.1模型二的建立
一、目标函数的导出
与问题一相似，从12个点所构成的点集中任选一个点作为起点，目标函数为权值的最小总和。
得总距离的最小值为：

二、约束条件的导出
根据题意，1营周围连接6个营点，2营点周围连接3个营点又每个营点必须和任意另外一个营点连接，由题中“在其他任意三个营节点遭到破坏通讯中断时，1营和12营仍然可以通讯”得1营点与12营点之间至少要有4个连通圈，与1营点连接的6个营点中，3营点与12营点没有不通过1营点本身的连通回路，1营点与11营点连接后欲与12营点形成回路必须通过营点4，所以确定4个连通圈为1营点分别与7营点、5营点、8营点、4营点连接即可。
故得出约束条件：
总边数在11到20之间：

1营点至少连接4个营点：

原题中与1营点关联的6个点的约束：

综上所述，问题二的优化模型为：

6.2.2模型二的求解
采用从起点1营到终点12营通过标号算法，分别求得第一条最短电缆路径1-5-12,。然后断开1-5,5-12使其达最大值，然后再采用标号算法求得第二条电缆路径1-8-2-12。同理断开1-8，8-2,2-12使其达最大值可得第三条路径1-4-9-12，和7-10-6-12,电缆路径，如图所示：

图五：问题二最优铺设电缆路线（单位千米）
得最小值为：13+21+14+29+27+17+18+5+23+20+26+15+35+45=308（千米）。

6.2.3模型二结果分析
按照以上最优解，从1营到12营之间铺设电缆构成网络,且分别是1-3,1-11,1-4,1-5,1-7,1-8,4-9,7-10,10-6,8-2,2-12,12-9,12-6,12-5,8-2,10-7两两互相连通，使得铺设电缆总长度最小为308km,12个大本营互通电缆的情况下，为了保证任意去掉3个军营1营和12营仍然保持通讯，1营与12营之间恰好有4条互不重合的路线，与上文的分析吻合，证实了分析的准确性。下面将结果图与原题图进行对比：

图六：问题二答案与原图的对比
通过将结果图与原题图进行对比，可以判断出结果合理。

6. 模型的评价
优点：
(1) 本题中将各营和各营之间的路线图抽象为，只含有点和边的无向图，使题中的信息表达更加清晰。
(2) 问题一中，首先由只有4个点的情况，推出只有4个点的模型，再跟据累比推理的原理，推出当有个点情况的模型。使本题模型的适用范围大大增广。
缺点：根据最小生成树算法建立的模型，并不适用于网络路径更加复杂的配电网环网架结构和开网运行的特点。

7. 模型的改进
Prim算法存在的缺陷：
最小生成树算法需要事先知道各边的权值，由于各边所选用电缆线的截面以及线损权值）在规划方案确定之前是无法知道的，所以提出以下算法的改进。
改进后的算法：
符号规定：
:加权图；
和：分别表示图中所有顶点和边的集合；
表示交叉点。
第一步：从，中选取具有最小权值的边，而将当作负荷点，则，。
第二步：从，中选出最小权值得边，则，。
第三步：从，中选出最小权值的边，将当作负荷点，则，。
第四步：从中选出最小权值的边，而将当作负荷点，则，。至此算法过程结束。

8. 模型的推广
一、横向推广：本题是对12个点的求解问题，由问题一的推广模型知，模型还适用于 个点的情况；
二、纵向推广：本题模型还可以运用于单向最优化路线问题等求解单向最短路线问题。

9. 参考文献
[1]陆于平，电网技术，东南大学出版社，2010,09.
[2]江波、张黎，计算机工程与设计，北京，北京邮电大学出版社，2009,13.
10. 附录
附录一：模型一求解源程序
%编程工具Matlab；
%这是一个通过避圈法求解连通带权图的最小生成树的程序.
n=input('请输入图的顶点数目:n= ')
W=input('请输入图的加权邻接矩阵:[W(1,1),..,W(1,n);..;W(n,1),..,W(n,n)]=')
%用W(i,i)="inf" 代替 "=0"
%准备工作
T=zeros(n); %最小生成树的加权邻接矩阵
WWW;
for i=1:n
for j=1:n
if W(i,j)==inf WW(i,j)=0;
end
end
end
m=((nnz(WW))/2); %图的边线的数目
j=0; %最小生成树的边线的数目
%主要步骤
for i=1:m %被选择边线的数目
if j<(n-1) %算法的终止条件是 |E|=|V|-1.
%步骤0: 挑选出权值最小的边 W(a,b)
min=inf; a=0; b=0;
for k=1:n
for l=(k+1):n
if W(k,l)<=min min=W(k,l); a=k; b=l; end
end
end
%步骤0 结束
%步骤1
%T=T+e(a,b)
T(a,b)=W(a,b); T(b,a)=W(a,b);
%检查是否有环的出现
f=0; %没有环的出现
P=zeros(2,m); y=0;
for i=1:n
for v=(i+1):n
if T(i,v)~=0 y=y+1; P1,y)=i; P(2,y)=v;
end
end
end
for y=1:m
if P(1,y));
elseif P(2,y)
end
end
if f==1 T(a,b)=0; T(b,a)=0; %转到 步骤2
else j=j+1; %转到 步骤3
end
W(a,b)=inf;
else %如果条件|E|=|V|-1成立
MST=T;
input('这个图的最小生成树的加权邻接矩阵是:')
MST
break
end
end
if j<(n-1) %如果条件|E|<|V|-1成立
input('这个图没有最小生成树.')
end
请输入图的顶点数目:n= 12

n =

12

请输入图的加权邻接矩阵:[W(1,1),..,W(1,n);..;W(n,1),..,W(n,n)]=[0 1000 35 20 27 1000 29 18 1000 1000 45 1000
1000 0 1000 1000 40 1000 1000 5 1000 1000 1000 23
35 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000
20 1000 1000 0 1000 1000 1000 15 26 1000 61 1000
27 40 1000 1000 0 31 1000 38 1000 16 1000 17
1000 1000 1000 1000 31 0 1000 1000 1000 21 1000 14
29 1000 1000 1000 1000 1000 0 1000 1000 13 1000 1000
18 5 1000 15 38 1000 1000 0 1000 1000 1000 1000
1000 1000 1000 26 1000 1000 1000 1000 0 1000 1000 15
1000 1000 1000 1000 16 21 13 1000 1000 0 1000 1000
45 1000 1000 61 1000 1000 1000 1000 1000 1000 0 89
1000 23 1000 1000 17 14 1000 1000 15 1000 89 0]

W =

Columns 1 through 8

0 1000 35 20 27 1000 29 18
1000 0 1000 1000 40 1000 1000 5
35 1000 0 1000 1000 1000 1000 1000
20 1000 1000 0 1000 1000 1000 15
27 40 1000 1000 0 31 1000 38
1000 1000 1000 1000 31 0 1000 1000
29 1000 1000 1000 1000 1000 0 1000
18 5 1000 15 38 1000 1000 0
1000 1000 1000 26 1000 1000 1000 1000
1000 1000 1000 1000 16 21 13 1000
45 1000 1000 61 1000 1000 1000 1000
1000 23 1000 1000 17 14 1000 1000

Columns 9 through 12

1000 1000 45 1000
1000 1000 1000 23
1000 1000 1000 1000
26 1000 61 1000
1000 16 1000 17
1000 21 1000 14
1000 13 1000 1000
1000 1000 1000 1000
0 1000 1000 15
1000 0 1000 1000
1000 1000 0 89
15 1000 89 0

这个图的最小生成树的加权邻接矩阵是:

MST =

0 0 35 0 0 0 0 18 0 0 45 0
0 0 0 0 0 0 0 5 0 0 0 23
35 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 15 0 0 0 0
0 0 0 0 0 0 0 0 0 16 0 17
0 0 0 0 0 0 0 0 0 0 0 14
0 0 0 0 0 0 0 0 0 13 0 0
18 5 0 15 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 15
0 0 0 0 16 0 13 0 0 0 0 0
45 0 0 0 0 0 0 0 0 0 0 0
0 23 0 0 17 14 0 0 15 0 0 0
附录二：模型二求解源程序
%mydistance,mypath]=mydijkstra(a,sb,db);
% 输入：a—邻接矩阵(aij)是指i到j之间的距离，可以是有向的
% sb—起点的标号, db—终点的标号
% 输出：mydistance—最短路的距离, mypath—最短路的路径
a=[0 1000 35 20 27 1000 29 18 1000 1000 45 1000
1000 0 1000 1000 40 1000 1000 5 1000 1000 1000 23
35 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000
20 1000 1000 0 1000 1000 1000 15 26 1000 61 1000
27 40 1000 1000 0 31 1000 38 1000 16 1000 17
1000 1000 1000 1000 31 0 1000 1000 1000 21 1000 14
29 1000 1000 1000 1000 1000 0 1000 1000 13 1000 1000
18 5 1000 15 38 1000 1000 0 1000 1000 1000 1000
1000 1000 1000 26 1000 1000 1000 1000 0 1000 1000 15
1000 1000 1000 1000 16 21 13 1000 1000 0 1000 1000
45 1000 1000 61 1000 1000 1000 1000 1000 1000 0 89
1000 23 1000 1000 17 14 1000 1000 15 1000 89 0];
sb=1;
db=12;
n=size(a,1);
visited(1:n) = 0;
distance(1:n) = inf; % 保存起点到各顶点的最短距离
distance(sb) = 0;
parent(1:n) = 0;
for i=1:4;
for i = 1: n-1;
temp=distance;
id1=find(visited==1); %查找已经标号的点
temp(id1)=inf; %已标号点的距离换成无穷
[t, u] = min(temp); %找标号值最小的顶点
visited(u) = 1; %标记已经标号的顶点
id2=find(visited==0); %查找未标号的顶点
for v = id2
if a(u, v) + distance(u) < distance(v)
distance(v) = distance(u) + a(u, v); %修改标号值
parent(v) = u;
end
end
end
mypath = [] ;
if parent(db) ~= 0 %如果存在路!
t = db;
mypath = [db];
while t ~= sb
p = parent(t);
mypath = [p mypath];
t = p;
end
end
%mypath(:,mypath(2:length(mypath-1)))=inf;
%mypath(mypath(2:length(mypath-1)),:)=inf;
end

mydistance = distance(db);
mydistance
mypath
return
%mydistance,mypath]=mydijkstra(a,sb,db);
% 输入：a—邻接矩阵(aij)是指i到j之间的距离，可以是有向的
% sb—起点的标号, db—终点的标号
% 输出：mydistance—最短路的距离, mypath—最短路的路径
a=[0 1000 35 20 1000 1000 29 18 1000 1000 45 1000
1000 0 1000 1000 40 1000 1000 5 1000 1000 1000 23
35 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000
20 1000 1000 0 1000 1000 1000 15 26 1000 61 1000
1000 40 1000 1000 0 31 1000 38 1000 16 1000 1000
1000 1000 1000 1000 31 0 1000 1000 1000 21 1000 14
29 1000 1000 1000 1000 1000 0 1000 1000 13 1000 1000
18 5 1000 15 38 1000 1000 0 1000 1000 1000 1000
1000 1000 1000 26 1000 1000 1000 1000 0 1000 1000 15
1000 1000 1000 1000 16 21 13 1000 1000 0 1000 1000
45 1000 1000 61 1000 1000 1000 1000 1000 1000 0 89
1000 23 1000 1000 1000 14 1000 1000 15 1000 89 0];
sb=1;
db=12;
n=size(a,1);
visited(1:n) = 0;
distance(1:n) = inf; % 保存起点到各顶点的最短距离
distance(sb) = 0;
parent(1:n) = 0;
for i=1:4;
for i = 1: n-1;
temp=distance;
id1=find(visited==1); %查找已经标号的点
temp(id1)=inf; %已标号点的距离换成无穷
[t, u] = min(temp); %找标号值最小的顶点
visited(u) = 1; %标记已经标号的顶点
id2=find(visited==0); %查找未标号的顶点
for v = id2
if a(u, v) + distance(u) < distance(v)
distance(v) = distance(u) + a(u, v); %修改标号值
parent(v) = u;
end
end
end
mypath = [] ;
if parent(db) ~= 0 %如果存在路!
t = db;
mypath = [db];
while t ~= sb
p = p