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

  1. 1、本文档共24页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
03‘斯坦纳最小树2课件

范例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)

文档评论(0)

gm8099 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档