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

《图的steiner最小树问题及其求解.docx》由会员分享，可在线阅读，更多相关《图的steiner最小树问题及其求解.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、er and Information Engineering, Henan University, Kaifeng 475001,China) Abstract: Steiner tree problem is one of the subject of combinatorial optimization problem. It belongs to NP-hard problems that cannt find the optimal solution in polynomial time. This article discusses the minimum steiner tree

3、problem in graphs, and gives the approximate algorithm, which is improved on loop damage method, and quoted the agents thinking. Finally, an analysis of the algorithm. Key words: steiner minimum tree; NP-hard problem; loop damage method 现实生活中常常要求解决这样的问题,即将若干给定点相连并使连线的总长最短。即最小生成树问题(Minimum Spanning T

4、reeMST)。最小生成树问题是运筹学、组合优化中的常见问题,即找寻一棵连接给定点并使树的总长度最短的生成树.若要求解n个点的最小生成树,一般我们首先想到的是求连接这n个点的最小生成树,扩展我们的思维,相象假如不拘泥于这n个点,我们再加入一些新点,是否会使我们的最小生成树更优呢?事实证明,假如不拘泥于这n个点,而引入除这n个点之外的另外几个点的话,则有可能使连接各区域的通信线路的总长更短。这是Steiner最小树问题的来源。 1 问题描述 图的Steiner最小树(Graphical Steiner Minimum Tree,简记GSMT)问题由Hakimi和Levin于11011年首次提出

5、。其定义为:给定无向图G=(V,E),其中V为点集,E为边集,边的权值(大于0)代表费用函数,假如现在有点集P?哿V,点集S?哿V,现在要求在网络中找寻一棵包含点集P中全部点的子树T,使得到的树T的费用最小。称T为图G关于P的steiner树,不属于P的点称为steiner点。这里要留意的一点,生成的steiner树的任steiner点的度都应当大于等于2。 在实际中有广泛的应用,例如,布置自然气管道时,当气源位置和用户的地理位置确定后,如何铺设管道使得管网布局最优问题。网络的有线通讯问题与通讯站点数量及其相互离亲密相关,通讯费用与线路长度成正比,因此有关如何布线以使整个网络达到连通要求且线路

6、最短的问题具有重要意义。通过增加“虚设”站点构造出Steiner最小树的方法能够有效解决这个问题。超大规模集成电路设计,交通线路规划,车辆调度与编组等都属于steiner最小树问题。 众所周知,Steiner树问题是NP-难的,除非P=NP,否则Steiner树问题没有多项式时间的算法。那么当输入规模很大时,我们就不行能在多项式时间内找到它的精确最优解。因此,我们起先致力于找到一个好的近似算法,给出好的近似解。 最小生成树是连接S点集中全部点的最小长度的树,它没有向给定的点集中插入任何额外的点,可以在O(n)时间内构造完成,并且是SMT的一个很好的近似。图的Steiner最小树的Steiner

7、比为1/2。 2 算法思想 寻求连通图支撑树的方法,任取一个圈,从圈中去掉一边,对余下的图重复这个步骤,直到不含圈时为止,即得到一个支撑树,称这种方法为破圈法 。 Agent是在肯定环境下能敏捷主动地完成某个任务的实体,它具有自主性、学习性、交互性 。 Agent的自主性是指能为将来目标预先行动,学习性是指能够将阅历转变为自己的学问,交互性是指不同Agent之间或者Agent与环境之间能够进行信息沟通。 令集合P为给定点集,S为待选点集(即steiner点,记为s-点),集合V=PS,顶点Vi与Vj间的距离记为d(vi,vj)。初始状态为给定的原点集P及P内顶点间的连接关系(边长,边集),若存

8、在边e(vi,vj),则两点间的距离d(vi,vj)即为此边的长度,若两点间不存在边则给此边一个高的惩处值。若对S中一个点Vs,存在边e(Vs, Vj),e(Vs, Vi),Vi, VjP,且d(Vs, Vi)+d(Vs, Vj)k add=1; for i=1 to agentNumber add=add_number-agenti.Number_of_steiner;/ 即目前已添加的s-点总数与当前要求达到的最大的s-点总数之间的差距 V=V+hyp; If (add0) /if 1 从集合S-hyp中随意选取add个s-点进行有关公式1的推断; 将使得公式1为真的点集temp加入集合V

9、; 重新计算集合V中随意两个原点Pi与Pj之间的最短距离,记为New_D(Pi,Pj); 计算,记为sum_Difference。 If sum_Difference0 agent.activity=true; 去除temp中度为1的点; hyp=hyp+temp; 修改Number_of_steiner的值; /end of if 1 /end of Test Diffuse() for every active agent A /suppose A select random agent B; /suppose B if (agentB.activity = =true) /if 2 if

10、(agentA.number_of_steiner = =agentB. number_of_steiner) /if 3 if (agentA.hyp = =agentB.hyp) agentB.hyp置为空集; agentB.activity=false; if(agentA.sum_difference A 复制 B的hyp及Steiner点数; if(agentA.sum_differenceagentB.sum_difference) B 复制 A的hyp及Steiner点数; /end of if 3 /end of if 2 end of Diffuse if add_numbe

11、rk add_number+; else 保存sum_difference最大的集合及状态; Break; 4 算法分析 如一家煤气公司要给多个城镇供应气源,如图1所示,现假定要给V1,V2,V3供应气源。其余的点为steiner点。为了寻求最优解,煤气公司现派若干人员去考查铺设管道的详细方案。最终采纳较优的方案。 通过多次试验,得到的树长最优值为8,如图2所示。树长最差值为10,树长平均值为8.924。 5 结束语 破圈法的时间困难度为O(n3),假如设agent的个数为m,则本算法的时间困难度为O(mn3)。本算法同时还涉及到设置多少个agent才合适的问题,设置的太多则影响算法的时间困难

12、度,相反则可能得不到预期的结果。agent的个数很难确定,所以算法还需改进。 参考文献: 1 Hakimi SL1Steiner problem in graphs and its imp lications1Networks,11011,1: 113-133. 2 Kou L, Markowsky G,Berman L1 A fast algorithm for Steiner trees1 Acta Info, 11011,15:141-145. 3 运筹学教材编写组.运筹学M.3版.北京:清华高校出版社,2022:258. 4 蔡自兴,徐光祐.人工智能及其应用M.3版.北京:清华高校出版社,2022: 315. 第7页 共7页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页