资源描述：
《Steiner最小树问题及其应用_张瑾》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第8卷第15期2008年8月科学技术与工程Vol18No115Aug.20081671-1819(2008)15-4238-09ScienceTechnologyandEngineeringZ2008Sci1Tech1Engng1综述数学Steiner最小树问题及其应用1,21张瑾马良(上海理工大学管理学院1,上海200093;河南大学计算机与信息工程学院2,开封475001)摘要Steiner最小树问题是一个历史悠久的经典的组合优化问题,由于应用广泛,多年来一直受到研究者的广泛关注。介绍了各种Steiner树问题及其求解算法和实际应用。关键词Steiner最小树精确算法启发式算法应用中图
2、法分类号O224;文献标志码A现实生活中经常要求解决这样的问题,即将若后经多位数学家扩展补充,最后以瑞士数学家Ste-i干给定点相连并使连线的总长最短。在网络通信ner的名字命名为Steiner问题。近年的数学史研究领域中,该问题被一般化地提为:如果要在n个区域又表明,Steiner问题还被大数学家Gauss研究过,间铺设通信网,使得各区域之间能实现信息的共Gauss有个做铁路工程师的儿子曾经问过其父亲如享,那么应如何铺设才能使通信线路的总长最短?何用最短的铁路将四座城市连起来,Gauss在回信一般首先想到的可能就是求连接这n个点的最小生中给出了详尽的解答。成树(MinimumSpanni
3、ngTree)MST)这种做法,但由于Steiner最小树问题在现代生产生活中应如果不拘泥于这n个点,而引入除这n个点之外的用十分广泛,因而多年来都是研究者关注的焦点。另外几个点的话,则有可能使连接各区域的通信线经典Steiner树问题大体包括欧氏的、绝对值距离路的总长更短。这是Steiner最小树问题(Steiner的、图的等几个重要方面,其中图的Steiner树应用MinimumTreeProblem,简记为SMTP)的来源。范围最广。Steiner最小树问题是经典的组合优化问题,最早可以追溯到17世纪初。1634年,数学家Fermat1平面上的Steiner最小树问题提出这样一个问题
4、:在欧氏平面上有三个点,寻找一个点使得由该点连接这三个点的距离之和最小。111问题定义目前研究最多的是平面上的Steiner最小树问2008年4月21日收到国家自然科学基金项目(70471065)、题,即给定二维平面上的点集P(其中的点称为原点上海市重点学科建设项目(T0502)资助或正则点),要求设法添加新点集S(其中的点称为第一作者简介:张瑾(1974)),女,河南开封人,博士生1研究方向:系统工程、智能优化。Steiner点,简称s-点),来构造平面上集合PGS的通信作者简介:马良(1964)),男,上海人,博士,教授,博士一棵最小生成树T,使其总长尽可能小于仅由P中生导师1研究方向
5、:智能优化。的点构成的最小生成树的长度。设p1=(x1,y1),15期张瑾,等:Steiner最小树问题及其应用4239p2=(x2,y2)为集合P中任意两点,则p1与p2间的d距离可表示为p1p2=(x1-x2+y1-y2d1/d)(d=1,2)。根据结点间连接方式的不同,可以分为两种:即当d=1时,结点间的距离为欧氏距离,此时的问题称为欧氏Steiner最小树(EuclideanSteinerMinimumTree)ESMT)问题;而当d=2时,性质5RSMT中任意s-点的关联边3,最大结点间的距离为绝对值距离(也称Manhattan距离,是4。结点间只能由直线段或折线段相连),此时
6、称为绝在RSMT中也有满Steiner树的概念,其定义与对值距离Steiner最小树(RectilinearSteinerMin-i[1)8]EFST相同,一个例外就是当原点数为4时,存在一mumTree)RSMT)问题。ESMT是最早研究的个Steiner点连接4个原点的情况。Steiner最小树问题,绝对值距离的Steiner最小树问[4]性质6对于平面上任意给定点集P,总存在题1966年由Hanan首次提出,下面是一些常用的一个绝对值距离Steiner最小树,且组成该RSMT的重要性质:所有满Steiner树只能是如图3所示的两种拓扑结性质1设平面上原点数为n个,则ESMT和构之一(
7、为明显起见,图中取原点数n=6)。RSMT均满足,s-点数[n-2。性质2ESMT上和s-点关联的边有三条,且这三条边中任意两条边夹角为120b。如果在欧氏距离下的一棵生成树T满足下列两个条件:(1)任一s-点必为由夹角等于120b的三条线段的交点;(2)n个原点的树中至多包含n-2个s-点,则称T为一个Steiner树,而称正好包含图4两种结构n-2个s-点的Steiner树为满Steiner树(FullSteiner
