steiner树1.ppt
- 文档编号:16625013
- 上传时间:2023-07-15
- 格式:PPT
- 页数:17
- 大小:202KB
steiner树1.ppt
《steiner树1.ppt》由会员分享,可在线阅读,更多相关《steiner树1.ppt(17页珍藏版)》请在冰点文库上搜索。
数学建模暑期培训,通讯网络的最佳Steiner树,一、问题二、假设三、问题分析四、问题求解算法五、计算结果,主要内容,穷举法构造型启发算法贪婪算法模拟退火法,给定平面上若干通讯站,两通讯站之间的线路长度为两点间的直角折线距离,即d=|x1-x2|+|y1-y2|两点间的线路费用正比于线路的长度。
如何布线使连接通讯站的线网费用最低。
通过引入若干“虚设站”并构造一个Steiner树就可降低由一组站生成的最小生成树所需的费用,为构造一个有n个站的网络,最低费用的Steiner树最多只需n-2个虚设站,这些虚设站称为Steiner点。
一、问题,假定要设计一个有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)。
一、问题,二、假设,1)通信站点集合V0是整数坐标的平面点集;2)两点间的距离为直角折线距离,线路费用正比于线路长度;3)虚设站位于格点(即坐标为整数的点)上。
例如:
设有三个通讯站,直角坐标分别为a(0,0),b(4,3),c(6,0)。
两点间的距离为直角折线距离。
以这三个站为顶点,距离为边权的加权完全图见左下图。
右下图是增加了一个“虚设站”后,得到的费用更少的树图。
三、问题分析,Z2:
平面上所有格点的集合;V0:
Z2中给定的n个通信站点的集合Vs;Vs:
Z2中任意s个点的集合,且VsV0=。
点集V0的最小Steiner树:
以V=VsV0为顶点集的完全图Ks+n,其中的边uv的权取为点u与v之间的直角折线距离,得到一个赋权完全图,其最小生成树记为TVs。
对任意非负整数s和任意点集Vs,所有TVs中权最小者记为T*,T*即为最小Steiner树。
T*中不属于V0的点称为Steiner点。
特别,s=0时的TV0称为V0的最小支撑树。
三、问题分析,1.基本概念,
(1)T*中包含多少个Steiner点(即虚设站);
(2)Steiner点的位置如何;(3)是否可能建立有效算法,以及如何解决该问题。
三、问题分析,2.几个小问题,定理1设T*是n个给定点的所有最小Steiner树中Steiner点个数s最小的,则sn-2。
三、问题分析,3.已有的结论,定理2Steiner点位于给定通信站点的x坐标线,y坐标线形成的格点上。
推论:
最多有n2-n=n(n-1)个Steiner点的可能位置,定理3求n个点的最小Steiner树的问题是NPC问题。
令C,从mn(n-1)个可能的Steiner点位置中任取s个点,s=0,1,2,.,n-2,将取到的s个点与给定的n个点合并,构造以这n+s个点为顶点的赋权完全图G(图中边权取为两点间的直角折线距离)用Kruskal算法,求G的最小生成树Ts及其费用Cs。
若CsC,则CCs,TTs.从m个点中另取s个点重复2),3)直到穷尽m个点中所有可能的点组合。
四、问题求解算法,1.穷举法,共需进行,四、问题求解算法,1.穷举法,次迭代。
若m不大,此法可行,否则若m大,此法将无效。
对给定的9个通讯站,m可减少到31个,从而,共需进行3572224次迭代,设每次迭代需要0.017秒,3572224次迭代需花大约17个小时。
定理4设V0=vi(xi,yi):
i=1,2,.,n,对每个yk,k=1,2,.,n,记,四、问题求解算法,1.穷举法,则在下述四类区域中不含Steiner点:
1.穷举法,定理4说明四个角点位置也不可能有Steiner点。
如图,星号点是给定的9个通讯站点。
根据定理2,共有n(n-1)=72个Steiner点的可能位置。
再根据定理4,区域D1,D2,D3和D4内不含Steiner点。
由此可确定,对给定的9个点,只有31个可能的Steiner点位置(图中小圆圈所示的31个位置),m=31。
四、问题求解算法,
(1)求给定的n个点上的最小支撑树,记录其费用;
(2)取一个可能的Steiner点加入,求最小支撑树;(3)若该树的费用小于当前的最小费用,则记录此树并更新费用;(4)重复
(2)到(4)直到已有n-2个Steiner点,或任何剩余的Steiner点加入都不能减少费用。
2.构造型启发算法,四、问题求解算法,
(1)输入给定的n个通信站点的坐标;
(2)计算最小直角折线支撑树;(3)找重边,则重边的端点便是Steiner点的侯选点;(4)分别计算出每个侯选点作为Steiner点加入后所减少的费用,该费用称为此点的价值;(5)把最大价值的侯选点也作为一个给定点,重复
(2)到(5)直到没有正价值的侯选点。
3贪婪算法,
(1)给定点集连同一些虚设点一起构成点集Z,求Z的最小支撑树,其费用记为C,置k=0;
(2)产生新的点集S从以下几种方式中随机选择一种:
加入一个新的虚设点去掉一个存在的虚设点移动一个现有的虚设点到一个随机的允许位置(3)确定新点集S的最小支撑树,其费用记为C1,若C1C,则更新C为C1,更新当前点集Z为S,当k=M时停止,否则k=k+1,转
(2);若C1C,则仅以一定的概率(可取为exp-(C1-C)/T(k),其中T为一控制参数,称为温度,随k的增大而减小,比如取T(k)=T(0)/k,称为冷却方案)接受S作为当前点集Z,转
(2)。
4.模拟退火法,五、计算结果,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- steiner