《斯坦纳最小树》由会员分享，可在线阅读，更多相关《斯坦纳最小树（24页珍藏版）》请在金锄头文库上搜索。
1、范例2 通讯网络的最佳Steiner树,1.问题 2.假设 3.问题分析及模型 4.问题求解 穷举法 贪婪试探算法 改进型试探算法 模拟退火法 修正的Prim启发式算法 5.结果,1.问题,给定平面上若干通讯站，两通讯站之间的线路长度为两点间的直角折线距离，即 d=|x1-x2|+|y1-y2| 两点间的线路费用正比于线路的长度。 如何布线使连接通信站的线网费用最低？ 如何构造最小Steiner树，即最低费用的Steiner树？,Steiner树：,Steiner树通过加入若干“虚设站”后，构造出由原站点和虚设站生成的最小生成树。若虚设站设置得恰当，就可降低由原站点生成的最小生成树所需的费用。
2、用这种方法可降低费用多达13.4% 注意： 1）Steiner树允许线路在通讯站点以外连接，这种连接点即为虚设站。 2）为构造一个有n个站的网络，最低费用的Steiner树最多只需n-2个虚设站，这些虚设站称为Steiner点。Steiner 点位于给定通信站点的x坐标线，y坐标线形成的格点上。,问题,假定要设计一个有9个通讯站点的局部网络，使其造价最低。这9个站的直角坐标为： a(0,15), b(5,20), c(16,24), d(20,20), e(33,25), f(23,11), g(35,7), h(25,0), i(10,3)。 求出联结这9个通讯站的最小Steiner树。,2
3、.假设,1）通信站点集合V0是整数坐标的平面点集； 2）两点间的距离为直角折线距离，线路费用正比于线路长度； 3）允许通讯线在非站点处连接。,3.问题分析及模型,给定n个通讯站点，用通讯线把这些站点联结起来，允许通讯线在非站点处连接，如何连接，可使连接通信站的线网费用最低？ 允许通讯线在站点以外的点（即“虚设站”或Steiner点）连接，这样可以使线网费用降低，但问题要复杂得多。 如，有三个通讯站，直角坐标分别为a(0,0), b(4,3),c(6,0),图13.5,图13.6,“虚设站”（即Steiner点）的个数和位置是解决问题的关键。 “Steiner点位于给定通信站点的x坐标线，y坐标
4、线形成的格点上”，最多有n2-n=n(n-1)个Steiner点的可能位置，这些位置就是Steiner点的候选点. 当n=9时，有n(n-1)=72个Steiner点的可能位置 V0 ：给定的n个通信站点的集合； Vp : Steiner点的候选点集合，设其点数为p, VpV0=； 以V= VpV0为顶点集作一个加权完全图Kp+n，其中的边(u,v)的权取为点u与v之间的直角折线距离。问题成为：求加权完全图Kp+n中包含V0（也允许包含V中的其他点）的权最小的子树。此即求加权完全图Kp+n中，V0的最小Steiner树问题。,求V0的最小Steiner树可分解为两个问题： 1）求Steiner
5、点；2）求最小生成树。 根据提示“最小Steiner树最多只需n-2个虚设站（Steiner点）”， Vs ：表示Vp中任意s个点的集合。 对满足0sn-2的整数s和点集Vs Vp，以V= VsV0为顶点集的加权完全图Ks+n的最小生成树记为Ts, 所有Ts 中权最小者记为T*，T*即为所要求的最小Steiner树。,(1)穷举法,求最小Steiner树问题是NP难题，点数较小的问题可用穷举法，但若规模较大，应寻求近似算法。 由于费用最少的Steiner树T*上最多只需引入n-2个虚设点，因此可从mn(n-1)个可能的Steiner点位置中任取s个点，s=0,1,2,n-2，连同给定的n个点一
6、起，用Kruskal算法，求由这n+s个点确定的赋权完全图（图中边权取为两点间的直角折线距离）的最小生成树Ts。 若m不大，此法可行，若m大，此法将无效。,在下述四类区域中不含Steiner点,如图13.7，星号点是给定的9个通讯站点。共有n(n-1)=72个Steiner点的可能位置，它们位于过9个点的水平线与垂直线的交点上。且由于区域D1,D2,D3和D4内不含Steiner点，72个可能的Steiner点位置可减少到31个（图4中小圆圈所示的31个位置）。 m=31,迭代次数减少到 次。假设每次迭代只需用1/60秒的时间，3572224次迭代需要大约17个小时。,9个给定点和31个可能的
7、 Steiner点 a(0,15), b(5,20), c(16,24), d(20,20), e(33,25), f(23,11), g(35,7), h(25,0), i(10,3),(2)贪婪试探算法,图13.5的最小生成树如图13.8（a），顶点按直角坐标之定位放置，右边的图是把边画成直角折线，该图称为其三个点的最小直角折线支撑树。若将图13.8的右边图中重边的端点d作为虚设站加入，则4个点的最小生成树的权减少了2。,图13.8,一般情况下，可把最小直角折线支撑树中重边的端点作为Steiner点的侯选点。结合贪婪法的思想，可构造出如下的试探法，能否得到正确解，需要证明。 1）输入给定的
8、n个通信站点的坐标； 2）计算最小直角折线支撑树； 3）找重边，则重边的端点便是Steiner点的侯选点； 4）分别计算出每个侯选点作为Steiner点加入后所减少的费用，该费用称为此点的价值； 5）把最大价值的侯选点也作为一个给定点，重复2)到5)直到没有正价值的侯选点。,(3)改进型试探算法,如果每次迭代，都按照随意的顺序加入“虚设站”，并使得到的最小生成树费用有所减少，直到已加入n-2个“虚设站”，或加入任何一个剩余的可能的Steiner点都不能使费用减少为止。按步骤描述如下 1）求给定的n个点的最小生成树，记录其费用； 2）取一个可能的Steiner点加入，求最小生成树，若该树的费用小
9、于当前的费用，则记录此树并更新费用； 3）重复2）直到已有n-2个Steiner点，或任何剩余的Steiner点加入都不能减少费用。 贪婪试探算法和改进型试探算法都是近似算法，对一般的问题未必能得到最优解。,(4)模拟退火法,这是一种通用的随机搜索法，是解决NPH问题的比较有效的方法。 1）给定点集连同一些虚设点一起构成点集Z，求Z的最小支撑树，其费用记为C，置k=0； 2）产生新的点集S 从以下几种方式中随机选择一种： 加入一个新的虚设点 去掉一个存在的虚设点 移动一个现有的虚设点到一个随机的允许位置,3）确定新点集S的最小支撑树，其费用记为C1， 若C1C，则更新C为C1，更新当前点集Z为
10、S, 当k=M时停止，否则k=k+1,转2); 若C1C，则仅以一定的概率（可取为exp-(C1-C)/T(k)，其中T为一控制参数，称为温度，随k的增大而减小,比如取T(k)=T(0)/k，称为冷却方案）接受S作为当前点集Z，转2)。,用模拟退火法来求图13.4所给出的9个点的最小Steiner树，在25MHz型386计算机上运行，大约1.5分中便可得到了最优解。 对应于随机数产生器的不同种子的不同运行，可给出全部五个不同的最优解。 在上百次运行中，模拟退火法都总是收敛到五个最优解中的一个。 计算时间方面的优越性表明当该问题的规模较大，穷举法不可行时，模拟退火法的价值。,(5)修正的Prim
11、启发式算法,受到求最小生成树的Prim算法的启发，根据Prim算法的思想，构造出下面的求最小直角折线Steiner树的方法。 先引入一些记号： Z： 给定的通讯站点集合； G： 给定通信站点的x坐标线，y坐标线形成的格点全体构成的集合； T： 当前Steiner树的顶点集； S=G-Z； 算法步骤： 1）选取Z中距离最近的两点zi=(xi,yi), zj=(xj,yj)；,2）这两点的x坐标或y坐标相同，则将两点连接起来，并把该路径上所有在G中的点以及zi,zj加入T，否则 a）构造过(xi,yj)的连接zi,zj的直角折线路径path1,将path1上所有属于G的点以及zi,zj加入T； b
12、）在Z-T中找到与当前树距离最近的顶点z，其距离记为dist1，然后删掉树中的path1； c）构造过(xi,yj)的连接zi,zj的直角折线路径path1, 将path1上所有属于G的点以及zi,zj加入T； d）在Z-T中找到与当前树距离最近的顶点z，其距离记为dist2，然后删掉树中的path2；,e）若dist1dist2, 则加入path1, 若dist2dist1, 则加入path2, 若dist1=dist2, 则对下一个最近点重复(2)a到(2)e, 直到dist1dist2, 或穷尽了Z中所有顶点（此时任意选择）； 3）取ziZ(G-T),zjT,使zi,zj尽可能近； 4）
13、重复2），3）直到Z中的顶点均在T中。,提示： 最小Steiner树问题是NP难题。 前面介绍的方法，除穷举法之外，每个算法都是有效算法，但不一定能得到最优解，一般需要对解的近似程度进行分析。 对算法的好坏，可随机给出一些通讯站，用这些方法来求解，对算法给出的解进行比较，看哪个算法效果最佳。,编写贪婪试探算法、改进型试探算法的MATLAB程序，求给定的9个通讯站的最小Steiner树。 用手工操作的方式，由修正的Prim启发式算法求给定的9个通讯站的最小Steiner树，体会该算法的思想。,结果,用穷举法可得到给定的9个通讯站的最小Steiner树，共有5个，费用为94。图13.9给出了这5个最小Steiner树，其中每个Steiner树都含4个或5个Steiner点。因此可按图13.9中任何一个Steiner树来设计给定9个站的费用最少的局部网络。,图13.9,
