图的steiner最小树问题及其求解
摘要:斯坦纳树问题是组合优化学科中的一个问题。属于NP-难问题,即无法在多项式时间内得到最优解。本文主要讨论了图的steiner最小树问题,并给出了近似算法,该算法是在破圈法的基础上进行了改进,并且引用了agent的思想。最后对算法进行了分析。
关键词:Steiner最小树 NP-难题 破圈法
中图分类号:TP312文献标识码:A文章编号:1009-3044(2009)25-7312-02
Graphical Steiner Minimum Tree Problem and Solusion
YANG Ling-yun
(College of Computer 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 cann’t find the optimal solution in polynomial time. This article discusses the minimum steiner tree problem in graphs, and gives the approximate algorithm, which is improved on loop damage method, and quoted the agent"s thinking. Finally, an analysis of the algorithm.
Key words: steiner minimum tree; NP-hard problem; loop damage method
现实生活中经常要求解决这样的问题,即将若干给定点相连并使连线的总长最短。即最小生成树问题(Minimum Spanning Tree—MST)。最小生成树问题是运筹学、组合优化中的常见问题,即寻找一棵连接给定点并使树的总长度最短的生成树.若要求解n个点的最小生成树,一般我们首先想到的是求连接这n个点的最小生成树,扩展我们的思维,相象如果不拘泥于这n个点,我们再加入一些新点,是否会使我们的最小生成树更优呢?事实证明,如果不拘泥于这n个点,而引入除这n个点之外的另外几个点的话,则有可能使连接各区域的通信线路的总长更短。这是Steiner最小树问题的来源。
1 问题描述
图的Steiner最小树(Graphical Steiner Minimum Tree,简记GSMT)问题由Hakimi和Levin于1971年首次提出 。其定义为:给定无向图G=(V,E),其中V为点集,E为边集,边的权值(大于0)代表费用函数,假如现在有点集P?哿V,点集S?哿V,现在要求在网络中寻找一棵包含点集P中所有点的子树T,使得到的树T的费用最小。称T为图G关于P的steiner树,不属于P的点称为steiner点。这里要注意的一点,生成的steiner树的任steiner点的度都应该大于等于2。
在实际中有广泛的应用,例如,布置天然气管道时,当气源位置和用户的地理位置确定后,如何铺设管道使得管网布局最优问题。网络的有线通讯问题与通讯站点数量及其相互离密切相关,通讯费用与线路长度成正比,因此有关如何布线以使整个网络达到连通要求且线路最短的问题具有重要意义。通过增加“虚设”站点构造出Steiner最小树的方法能够有效解决这个问题。超大规模集成电路设计,交通线路规划,车辆调度与编组等都属于steiner最小树问题。
众所周知,Steiner树问题是NP-难的,除非P=NP,否则Steiner树问题没有多项式时间的算法。那么当输入规模很大时,我们就不可能在多项式时间内找到它的精确最优解。因此,我们开始致力于找到一个好的近似算法,给出好的近似解。
最小生成树是连接S点集中所有点的最小长度的树,它没有向给定的点集中插入任何额外的点,可以在O(㏒n)时间内构造完成,并且是SMT的一个很好的近似。图的Steiner最小树的Steiner比为1/2。
2 算法思想
寻求连通图支撑树的方法,任取一个圈,从圈中去掉一边,对余下的图重复这个步骤,直到不含圈时为止,即得到一个支撑树,称这种方法为破圈法 。
Agent是在一定环境下能灵活主动地完成某个任务的实体,它具有自主性、学习性、交互性 。 Agent的自主性是指能为将来目标预先行动,学习性是指能够将经验转变为自己的知识,交互性是指不同Agent之间或者Agent与环境之间能够进行信息交流。
令集合P为给定点集,S为待选点集(即steiner点,记为s-点),集合V=P∪S,顶点Vi与Vj间的距离记为d(vi,vj)。初始状态为给定的原点集P及P内顶点间的连接关系(边长,边集),若存在边e(vi,vj),则两点间的距离d(vi,vj)即为此边的长度,若两点间不存在边则给此边一个高的惩罚值。若对S中一个点Vs,存在边e(Vs, Vj),e(Vs, Vi),Vi, Vj∈P,且d(Vs, Vi)+d(Vs, Vj) 对s-点的选择是从S集合中随机选择。 3 求解步骤 定义一个agent类,设置若干个agent对象,初始状态V=P,计算P中任意两个原点Pi与Pj之间的最短距离,记为Old_D(Pi,Pj)。最多添加的s-点总数为k。当前每个agent.hyp集合中可以包含的s-点总数的上界为add_number(0≤add_num≤m, 1≤m≤k),初始值为1。 Class agent { int Number_of_steiner; //当前已经添加s-点的个数 item hyp;// 保存其设想添加的s-点集合 float sum_difference; bool activity; //agent的状态 }; Initialize agent:每个agent.hyp初始化为空集,s-点的个数为0,Sum_Difference为0。 Repeat { Test(){ if add>k add=1; for i=1 to agentNumber { add=add_number-agent[i].Number_of_steiner;// 即目前已添加的s-点总数与当前要求达到的最大的s-点总数之间的差距 V=V+hyp; If (add>0) { //if 1 从集合S-{hyp}中任意选取add个s-点进行有关公式1的判断; 将使得公式1为真的点集temp加入集合V; 重新计算集合V中任意两个原点Pi与Pj之间的最短距离,记为New_D(Pi,Pj); 计算,记为sum_Difference。 If sum_Difference>0{ 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(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_difference>agentB.sum_difference) B 复制 A的hyp及Steiner点数; }//end of if 3 }//end of if 2 } end of Diffuse if add_number 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才合适的问题,设置的太多则影响算法的时间复杂度,相反则可能得不到预期的结果。agent的个数很难确定,所以算法还需改进。 参考文献: [1] Hakimi SL1Steiner problem in graphs and its imp lications1Networks,1971,1: 113-133. [2] Kou L, Markowsky G,Berman L1 A fast algorithm for Steiner trees1 Acta Info, 1981,15:141-145. [3] 《运筹学》教材编写组.运筹学[M].3版.北京:清华大学出版社,2005:258. [4] 蔡自兴,徐光祐.人工智能及其应用[M].3版.北京:清华大学出版社,2007: 315.
