§12—4，§12—5
用最小生成树解决通信网络的优化设计问题一．问题提出
建一个局部通信网：9个通信站坐标(0.15),(5,20),（略写）……,(10,3)；铺设通信线缆使这9个点连通，其线路按平行于坐标轴的直角折线方式行进。优化目标：通信线缆总长最短。
二．问题分析
1．直角折线？
两个站点(0.15),(5,20)之间的连接长度为5+5=10.
任意两点(a,b),(x,y)的“直角折线距离”定义为：
2．选择连接点？
9个站点记为，图示：
引例：只考虑右下角三个站(23,11),(25,0),(35,7)连通，增加一个连接点(25,7)可得总长度最小值23；若有规定“不准在通信站之外的点连接”，则总长度最小值为(11+2)+(12+4)=29,
分两种情况建立模型：（1）简化情况，不准在通信站之外的点连接，（2）实用情况，允许在通信站之外的点连接。
三．简化的模型
规定不准站外连接，则问题的模型就是：以9个站为顶点的完备赋权图G，任意两站之间的直角折线距离就是对应边的权，该图的最小生成树即为所求。
下面用Matlab求解该模型。
构造,加权邻接矩阵a”，（syp179ljjz.m）
clear
x0=[0,5,16,20,33,23,35,25,10];
y0=[15,20,24,20,25,11,7,0,3];
for i=1:9
for j=1:9
a(i,j)=abs(x0(i)-x0(j))+abs(y0(i)-y0(j));
end
end
2．“加权邻接矩阵”a转换成“边权矩阵”b
a中的对应于b的一个列，该列的三个元素分别为，问题是你把该列放在b的第几列？ 下面程序（syp179bqjz.m）实现这个转换：
k=0;
for i=1:8
for j=i+1:9
k=k+1;
b(:,k)=[i;j;a(i,j)];
end
end
3．用Kruskal算法计算最小生成数
上次内容，已经建立好用Kruskal算法给出最小生成数的函数文件syp175hswj(b)，其中b是须准备好的边权矩阵，现在只需调用它即可，[T,quan]=syp175hswj(b)
输出最小生成数T：
T =
3 4 8
1 2 10
4 6 12
6 8 13
2 3 15
6 7 16
3 5 18
8 9 18
quan =110
4．图示结果（syp180tushi.m）
hold on
for i=1:9
plot(x0(i),y0(i),'*')
end
for k=1:8
plot([x0(T(k,1)),x0(T(k,1))],[y0(T(k,1)),y0(T(k,2))])
plot([x0(T(k,1)),x0(T(k,2))],[y0(T(k,2)),y0(T(k,2))])
end
grid,hold off
四．实用的模型
允许在通信站之外的点连接，下图中的非站点网格结点（共个）称为“虚设站”。从这63个点中任取k个(k=0,1,2,…,63)与9个真站共同组成一个含(9+k)个顶点的完备图，其最小生成树称为Steiner树。有很多个Steiner树，权最小的称为最小Steiner树。
结论：含n个真站的网络，其最小Steiner树所含的“虚设站”不超过(n-2)个。
若用遍历法选取“虚设站”，则从n(n-1)中任取k个，k=0,1,…,(n-2)，工作量是巨大的天文数字。
读书P181----P188
用最小生成树解决通信网络的优化设计问题一．问题提出
建一个局部通信网：9个通信站坐标(0.15),(5,20),（略写）……,(10,3)；铺设通信线缆使这9个点连通，其线路按平行于坐标轴的直角折线方式行进。优化目标：通信线缆总长最短。
二．问题分析
1．直角折线？
两个站点(0.15),(5,20)之间的连接长度为5+5=10.
任意两点(a,b),(x,y)的“直角折线距离”定义为：
2．选择连接点？
9个站点记为，图示：
引例：只考虑右下角三个站(23,11),(25,0),(35,7)连通，增加一个连接点(25,7)可得总长度最小值23；若有规定“不准在通信站之外的点连接”，则总长度最小值为(11+2)+(12+4)=29,
分两种情况建立模型：（1）简化情况，不准在通信站之外的点连接，（2）实用情况，允许在通信站之外的点连接。
三．简化的模型
规定不准站外连接，则问题的模型就是：以9个站为顶点的完备赋权图G，任意两站之间的直角折线距离就是对应边的权，该图的最小生成树即为所求。
下面用Matlab求解该模型。
构造,加权邻接矩阵a”，（syp179ljjz.m）
clear
x0=[0,5,16,20,33,23,35,25,10];
y0=[15,20,24,20,25,11,7,0,3];
for i=1:9
for j=1:9
a(i,j)=abs(x0(i)-x0(j))+abs(y0(i)-y0(j));
end
end
2．“加权邻接矩阵”a转换成“边权矩阵”b
a中的对应于b的一个列，该列的三个元素分别为，问题是你把该列放在b的第几列？ 下面程序（syp179bqjz.m）实现这个转换：
k=0;
for i=1:8
for j=i+1:9
k=k+1;
b(:,k)=[i;j;a(i,j)];
end
end
3．用Kruskal算法计算最小生成数
上次内容，已经建立好用Kruskal算法给出最小生成数的函数文件syp175hswj(b)，其中b是须准备好的边权矩阵，现在只需调用它即可，[T,quan]=syp175hswj(b)
输出最小生成数T：
T =
3 4 8
1 2 10
4 6 12
6 8 13
2 3 15
6 7 16
3 5 18
8 9 18
quan =110
4．图示结果（syp180tushi.m）
hold on
for i=1:9
plot(x0(i),y0(i),'*')
end
for k=1:8
plot([x0(T(k,1)),x0(T(k,1))],[y0(T(k,1)),y0(T(k,2))])
plot([x0(T(k,1)),x0(T(k,2))],[y0(T(k,2)),y0(T(k,2))])
end
grid,hold off
四．实用的模型
允许在通信站之外的点连接，下图中的非站点网格结点（共个）称为“虚设站”。从这63个点中任取k个(k=0,1,2,…,63)与9个真站共同组成一个含(9+k)个顶点的完备图，其最小生成树称为Steiner树。有很多个Steiner树，权最小的称为最小Steiner树。
结论：含n个真站的网络，其最小Steiner树所含的“虚设站”不超过(n-2)个。
若用遍历法选取“虚设站”，则从n(n-1)中任取k个，k=0,1,…,(n-2)，工作量是巨大的天文数字。
读书P181----P188
