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