图的steiner最小树问题及其求解

1、steiner最小树问题及其求解摘要:斯坦纳树问题是组合优化学科中的一个问题。属于NP-难问题，即无法在多项式时间内得到最优解。本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进，并且引用了agent的思想。最后对算法进行了分析。关键词：Steiner最小树NP-难题破圈法中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)25-7312-02GraphicalSteinerMinimumTreeProblemandSolusionYANGLing-yun(CollegeofComputerandInformationEng

2、ineering,HenanUniversity,Kaifeng475001,China)Abstract:Steinertreeproblemisoneofthesubjectofcombinatorialoptimizationproblem.ItbelongstoNP-hardproblemsthatcanntfindtheoptimalsolutioninpolynomialtime.Thisarticlediscussestheminimumsteinertreeproblemingraphs,andgivestheapproximatealgorithm,whichisimprov

3、edonloopdamagemethod,andquotedtheagent'sthinking.Finally,ananalysisofthealgorithm.Keywords:steinerminimumtree;NP-hardproblem;loopdamagemethod现实生活中经常要求解决这样的问题,即将若干给定点相连并使连线的总长最短。即最小生成树问题(MinimumSpanningTree-MST)。最小生成树问题是运筹学、组合优化中的常见问题,即寻找一棵连接给定点并使树的总长度最短的生成树.若要求解n个点的最小生成树,一般我们首先想到的是求连接这n个点的最小生成树,

4、扩展我们的思维,相象如果不拘泥于这n个点,我们再加入一些新点,是否会使我们的最小生成树更优呢?事实证明,如果不拘泥于这n个点,而引入除这n个点之外的另外几个点的话,则有可能使连接各区域的通信线路的总长更短。这是Steiner最小树问题的来源。1 问题描述图的Steiner最小树(GraphicalSteinerMinimumTree,简记GSMT)问题由Hakimi和Levin于1971年首次提出。其定义为:给定无向图G=(V,E),其中V为点集，E为边集，边的权值(大于0)代表费用函数，假如现在有点集P?普V,点集S?普V,现在要求在网络中寻找一棵包含点集P中所有点的子树T,使得到的树T的费

5、用最小。称T为图G关于P的steiner树,不属于P的点称为steiner点。这里要注意的一点，生成的steiner树的任steiner点的度都应该大于等于2。在实际中有广泛的应用,例如,布置天然气管道时,当气源位置和用户的地理位置确定后,如何铺设管道使得管网布局最优问题。网络的有线通讯问题与通讯站点数量及其相互离密切相关,通讯费用与线路长度成正比,因此有关如何布线以使整个网络达到连通要求且线路最短的问题具有重要意义。通过增加“虚设”站点构造由Steiner最小树的方法能够有效解决这个问题。超大规模集成电路设计,交通线路规划,车辆调度与编组等都属于steiner最小树问题。众所周知，Stein

6、er树问题是NP-难的，除非P=NP,否则Steiner树问题没有多项式时间的算法。那么当输入规模很大时,我们就不可能在多项式时间内找到它的精确最优解。因此,我们开始致力于找到一个好的近似算法,给出好的近似解。最小生成树是连接S点集中所有点的最小长度的树,它没有向给定的点集中插入任何额外的点，可以在O(?Sn)时间内构造完成，并且是SMT的一个很好的近似。图的Steiner最小树的Steiner比为1/2。2 算法思想寻求连通图支撑树的方法,任取一个圈,从圈中去掉一边,对余下的图重复这个步骤,直到不含圈时为止,即得到一个支撑树,称这种方法为破圈法。Agent是在一定环境下能灵活主动地完成某个任

7、务的实体,它具有自主性、学习性、交互性。Agent的自主性是指能为将来目标预先行动,学习性是指能够将经验转变为自己的知识,交互性是指不同Agent之间或者Agent与环境之间能够进行信息交流。令集合P为给定点集，S为待选点集(即steiner点，记为s-点)，集合V=PUS,顶点Vi与Vj间的距离记为d(vi,vj)o初始状态为给定的原点集P及P内顶点间的连接关系(边长,边集),若存在边e(vi,vj),则两点间的距离d(vi,vj)即为此边的长度,若两点间不存在边则给此边一个高的惩罚值。若对S中一个点Vs,存在边e(Vs,Vj),e(Vs,Vi),Vi,Vj6P且d(Vs,Vi)+d(Vs,

8、Vj)kadd=1;fori=1toagentNumberadd=add_number-agenti.Number_of_steiner;/即目前已添加的s-点总数与当前要求达到的最大的s-点总数之间的差距V=V+hyp;If(add>0)/if1从集合S-hyp中任意选取add个s-点进行有关公式1的判断;将使得公式1为真的点集temp加入集合V;重新计算集合V中任意两个原点Pi与Pj之间的最短距离,记为New_D(Pi,Pj);计算,记为sum_Difference。Ifsum_Difference>0agent.activity=true;去除temp中度为1的点;hyp=hyp+temp;修改Number_of_steiner的值;/endofif1/endofTestDiffuse()foreveryactiveagentA/supposeAselectrandomagentB;/supposeBif(agentB.activity=true)/if2if(agentA.number_of_steiner=agentB.number_of_steiner)/if3if(agentA.hyp=agentB.hyp)agentB.hyp置为空集;agentB.activity=false;if(agentA.sum_