资源描述：
《斯坦纳最小树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、范例2通讯网络的最佳Steiner树1.问题2.假设3.问题分析及模型4.问题求解穷举法贪婪试探算法改进型试探算法模拟退火法修正的Prim启发式算法5.结果1.问题给定平面上若干通讯站，两通讯站之间的线路长度为两点间的直角折线距离，即d=
2、x1-x2
3、+
4、y1-y2
5、两点间的线路费用正比于线路的长度。①如何布线使连接通信站的线网费用最低？②如何构造最小Steiner树，即最低费用的Steiner树？Steiner树：Steiner树——通过加入若干“虚设站”后，构造出由原站点和虚设站生成的最小生成树。若虚设站设置得
6、恰当，就可降低由原站点生成的最小生成树所需的费用。用这种方法可降低费用多达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)
7、,g(35,7),h(25,0),i(10,3)。求出联结这9个通讯站的最小Steiner树。2.假设1）通信站点集合V0是整数坐标的平面点集；2）两点间的距离为直角折线距离，线路费用正比于线路长度；3）允许通讯线在非站点处连接。3.问题分析及模型给定n个通讯站点，用通讯线把这些站点联结起来，允许通讯线在非站点处连接，如何连接，可使连接通信站的线网费用最低？允许通讯线在站点以外的点（即“虚设站”或Steiner点）连接，这样可以使线网费用降低，但问题要复杂得多。如，有三个通讯站，直角坐标分别为a(0,0),b(4,
8、3),c(6,0)图13.5图13.6“虚设站”（即Steiner点）的个数和位置是解决问题的关键。“Steiner点位于给定通信站点的x坐标线，y坐标线形成的格点上”，最多有n2-n=n(n-1)个Steiner点的可能位置，这些位置就是Steiner点的候选点.当n=9时，有n(n-1)=72个Steiner点的可能位置V0：给定的n个通信站点的集合；Vp:Steiner点的候选点集合，设其点数为p,Vp∩V0=φ；以V=Vp∪V0为顶点集作一个加权完全图Kp+n，其中的边(u,v)的权取为点u与v之间的直角折
9、线距离。问题成为：求加权完全图Kp+n中包含V0（也允许包含V中的其他点）的权最小的子树。此即求加权完全图Kp+n中，V0的最小Steiner树问题。求V0的最小Steiner树可分解为两个问题：1）求Steiner点；2）求最小生成树。根据提示“最小Steiner树最多只需n-2个虚设站（Steiner点）”，Vs：表示Vp中任意s个点的集合。对满足0≤s≤n-2的整数s和点集VsVp，以V=Vs∪V0为顶点集的加权完全图Ks+n的最小生成树记为Ts,所有Ts中权最小者记为T*，T*即为所要求的最小Steiner
10、树。(1)穷举法求最小Steiner树问题是NP难题，点数较小的问题可用穷举法，但若规模较大，应寻求近似算法。由于费用最少的Steiner树T*上最多只需引入n-2个虚设点，因此可从m≤n(n-1)个可能的Steiner点位置中任取s个点，s=0,1,2,…,n-2，连同给定的n个点一起，用Kruskal算法，求由这n+s个点确定的赋权完全图（图中边权取为两点间的直角折线距离）的最小生成树Ts。若m不大，此法可行，若m大，此法将无效。在下述四类区域中不含Steiner点如图13.7，星号点是给定的9个通讯站点。共有
11、n(n-1)=72个Steiner点的可能位置，它们位于过9个点的水平线与垂直线的交点上。且由于区域D1,D2,D3和D4内不含Steiner点，72个可能的Steiner点位置可减少到31个（图4中小圆圈所示的31个位置）。m=31,迭代次数减少到次。假设每次迭代只需用1/60秒的时间，3572224次迭代需要大约17个小时。9个给定点和31个可能的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)
12、(2)贪婪试探算法图13.5的最小生成树如图13.8（a），顶点按直角坐标之定位放置，右边的图是把边画成直角折线，该图称为其三个点的最小直角折线支撑树。若将图13.8的右边图中重边的端点d作为虚设站加入，则4个点的最小生成树的权减少了2。图13.8一般情况下，可把最小直角折线支撑树中重边的端点作为Steiner点的侯选点。结合贪婪法的思想，可构造出如下的试探
