03‘斯坦纳最小树2课件.ppt

范例2 通讯网络的最佳Steiner树 1.问题 2.假设 3.问题分析及模型 4.问题求解 穷举法 贪婪试探算法 改进型试探算法 模拟退火法 修正的Prim启发式算法 5.结果 1.问题 给定平面上若干通讯站，两通讯站之间的线路长度为两点间的直角折线距离，即 d=|x1-x2|+|y1-y2| 两点间的线路费用正比于线路的长度。 ①如何布线使连接通信站的线网费用最低？ ②如何构造最小Steiner树，即最低费用的Steiner树？ Steiner树： Steiner树——通过加入若干“虚设站”后，构造出由原站点和虚设站生成的最小生成树。若虚设站设置得恰当，就可降低由原站点生成的最小生成树所需的费用。用这种方法可降低费用多达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.假设 1）通信站点集合V0是整数坐标的平面点集； 2）两点间的距离为直角折线距离，线路费用正比于线路长度； 3）允许通讯线在非站点处连接。 3.问题分析及模型 给定n个通讯站点，用通讯线把这些站点联结起来，允许通讯线在非站点处连接，如何连接，可使连接通信站的线网费用最低？ 允许通讯线在站点以外的点（即“虚设站”或Steiner点）连接，这样可以使线网费用降低，但问题要复杂得多。 如，有三个通讯站，直角坐标分别为a(0,0), b(4,3),c(6,0) “虚设站”（即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之间的直角折线距离。问题成为：求加权完全图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和点集Vs Vp，以V= Vs∪V0为顶点集的加权完全图Ks+n的最小生成树记为Ts, 所有Ts 中权最小者记为T*，T*即为所要求的最小Steiner树。 (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点 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) (2)贪婪试探算法 图13.5的最小生成树如图13.8（a），顶点按直角坐标之定位放置，右边的图是把边画成直角折线，该图称为其三个点的最小直角折线支撑树。若将图13.8的右边图中重边的端点d作为虚设站加入，则4个点的最小生成树的权减少了2。 一般情况下，可把最小直角折线支撑树中重边的端点作为Steiner点的侯选点。结合贪婪法的思想，可构造出如下的试探法，能否得到正确解，需要证明。 ??? 1）输入给定的n个通信站点的坐标； ??? 2）计算最小直角折线支撑树； ??? 3）