ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.260-264



ѵManhattanSteiner㷨
ܺ
ժҪѵManhattanSteiner(minimum rectilinear Steiner tree,ΪMRST)VLSIߡͨŻ,ͬʱҲһNP-ѽ.ĸԸO(n2)ʱ临ԵĽ㷨.㷨µĽƱϸС3/2.ʵ,õ֧ƽ㷨ƽý0.8%.㷨Լ޸,ӦõάάManhattanռSteiner,ڲֲʽ±ʵ.
ؼʣSteiner ,㷨,Ż,·.
ţO157
A Near-Optimal Approximation Algorithm for Manhattan Steiner Tree
MA JunYANG BoMA Shao-han
(Department of Computer Science Shandong University,Ji'nan,250100)
AbstractThe minimum rectilinear Steiner tree (MRST) problem is an NP-complete problem which arises in VLSI wiring,network routing and many combinatorial optimization problems.In this paper,an O(n2) time complexity approximation algorithm for MRST is proposed.The approximation ratio of the algorithm is strictly less than 3/2.The computer verification of the algorithm shows that the costs of the produced spanning trees are only 0.8% away from the optimal.In addition,this algorithm can be revised for multidimensional Manhattan space and implemented in parallel/distributed environments easily.
Key wordsSteiner tree,complexity theory,combinatorial optimization,circuit layout
MRST(minimum rectilinear Steiner tree)ɼΪ:ZΪƽϸn㼯,Zp1=(x1,y1),p2=(x2,y2),ֻˮƽ봹ֱֱ.ӳȶΪdist(p1,p2)=|x1-x2|+|y1-y2|1ݣΪManhattanռ룩.ƽϵһ㼯S,ԵõƽϵһT.TΪ֧ƽ涥㼯ZSС,,֧TķCOST(T)ΪTеıߵĳ֮ͣTΪSteinerSеĶ㱻ΪSteiner.SΪռ,TΪСminimum spanning tree,MST.ͼ14MSTӦSteiner.

Fig.1
ͼ1
MRSTһŻ,ڲߵõ˽Ϊ㷺Ӧã16.MRSTľȷNP-ȫ1,оMRSTп١߽ƱȵĽ㷨,һֱõǵ.,Hanan֤SΪͨZnˮƽ봹ֱֱγɵĽ㼯Ӽ,ͼ2ʾ3ݣSuyder֤˸ýڸάManhattanռҲ4ݣ,֤MSTΪMRSTһ൱õĽƽ,COST(MST)/COST(MRST)3/21.,ٻMST㷨˼MRSTĽ㷨1,ʹɵ֧ƽÿɱCOST(MST)79%1.Ȼ,Щ㷨µĽƱΪ3/2.,Ƿ½ƱϸС3/2㷨,ͳΪһ5.

Fig.2Hanan's theorem
ͼ2Hanan˵
ĸһµMRST㷨.,COST(T)/COST(MRST)<3/2.ϵʵ,㷨֧,ƽÿɱMSTĽ10.2%,ף6ƽ㷨ֵ,ƽ0.8%.
1㷨ʵ
,p,eֱʾƽϵһһ.peľdist(p,e)Ϊdist(p,p)Сֵ,pΪeϵⶥ.ڱeΪһ,Ԫ(p1,p2,p3)ʾe,p1,p3ֱʾe˵㡢p2ʾмĹ.ݼ,e,e֮ľ붨Ϊmin{dist(u,e),dist(v,e)|uΪeԪʾе֮һ,veԪʾе֮һ}.
ST㷨.Steiner㷨
:ƽ϶㼯ZĶĶά(xi,yi),1in.
:֧ZSTı߼SеSteiner.
ʹõıΪ:Զi=(xi,yi),V(i)(1)=xi;V(i)(2)=yiʾ.άԪW(i,j)Ϊi,j֮Manhattan.Ԫ(i,pi1,pi2),Pi1Pi2ֱʾZS-{i}оඥiʹĶ㣨pi1=pi2,Zֻһδʶ㣩.length(i,pi1,pi2)ʾ3MRSTķ.
 1.
(1.1) S:=;L:=.i,δ.i,jĶά,W(i,j).W,Ԫ(i,pi1,pi2).ͼ3ʾ3ӷ,ҳ,䳤ȼΪlength(i,pi1,pi2).

Fig.3The optimal connections for three vertices based on their positions
ͼ3λõӷ
(1.2) Zδʶ,ת2
(1.3) δʵĶ,ѰҶi,iĿǰСlength(i,pi1,pi2)ֵ,:
1.3δʹ,ǵ໥λ,ͼ3ʾӷ3ӣ3㱻ʹTi;ͼ3(a)(c),ѲSteinerS,ѲL.
2.,ѰiPi1Lеĳһϵĵıe,e䳤Ϊmin{dist(i,Pi1),dist(i,e),dist(i,e)|eΪL붥ıߣeǵߵeĴֱˮƽӴ֮õı}.eL,iPi1ͬͱʹǣeһ˵ΪSteiner,S.
(1.4) ÿ²Steineru,uδʶjľd(u,j);
if dist(u,j)<dist(j,pi2) then {
if dist(u,j)<dist(j,pi1) then {pi2=pi1;pi1=u;}
else pi2=u; endif;
޸ĶӦԪ(j,pi1,pi2)Length(j,pi1,pi2)ֵ.} endif;
(1.5) תִв(1.2).
2.ڲ1,γkT1,T2,...,Tk.e,eɲƽTiTj,ji߼֮Сӱ,1i<jk.ͨe鲢.eL,eһ˵ΪSteiner,䵽S.ظ,ֱƽֻһT.
3.Lеı߼COST(T)..
ݴͳĶMRST㷨ƶȵ۷1,5,6,Ƕǵ㷨MST㷨ͬһ֧ķýжԱ,1.nɼһƽ.aʾεı߳,r=COST(T)/COST(MST),sʾ㷨ʹõSteiner.
Table 1The performance of algorithm ST against MST algorithm
1С֧㷨뱾㷨ñȽ

na=100a=200
COST(MST)COST(T)srCOST(MST)COST(T)sr
1024421940.89754160051660.860000
20365322100.882192829744100.897467
30478414140.8661091093934140.854529
40541489170.9038821032960180.930233
50628567170.90286612211082170.886159
60631594230.94136312981178260.907550
70720654280.90833314781335250.903248
80762688320.90288715371400340.910865
90797724320.90840716141467330.908922
100872793450.90940417261577430.913673

 1ST㷨֧ƽ,ʹMSTнĽ10.2%.
2㷨۷
Ȼ,㷨STõһùZS֧T.㷨ST֧MSTĸĽԼST㷨ʱ临.
 2.1.|Z|4ʱ,COST(T)=COST(MRST).
֤:Ȼ,|Z|<3ʱ,|Z|=3ʱ,ȥԳ,ֻͼ3ʾ3ֹ3໥λ.CʾΧס3ĳRܳ,Ȼ,ͼ3ӷѡӵĳǡΪC/2,Ϊ3С,ΪһMRST.
|Z|=4ʱ,MRSTΪһ3ٵMRST,ʣһMRSTߵˮƽֱ,ǵ㷨ִͬ.Ҳ.
,֤.
֤̲ѿ,Ӧ3MST,COST(MST)C/2.
2.2.COST(T)COST(MST);COST(T)=COST(MST)ҽMSTһMRST.
֤:֤COST(T)COST(MST).2.1,|Z|4ʱ,.ʿ,|Z|>4.
MRSTǼƽϻManhattanSteiner,MRSTʵƽxy߶.HananĶ,MRSTͨƽʵ,ÿСƽֲMRST,Ȼͨʵ,õȫֵMRST.ڱ㷨,þܳĿΧסĿǰZSδʹ3v1,v2,v3ĳRƽ,RTi.2.1֪,TiΪRڵMRST.e=(v4,v5),ʾ㷨ʱTiһ,v4ΪTiĶ㣻v5ΪϵĶ.ST㷨(1.3)е2Ͳ2ִп֪,eΪTi̱.RʾΧס4v1,v2,v3,v5ĳ,RܳԺeΪv5Ti̱ԼKruskal㷨Աߵѡȡ7֪,RɵľֲMSTΪȫMSTһ.ǵ㷨ǻHananִ,ٳͼ3eTiӵ,㷨RɵáR϶ӦľֲMSTķ.RԼST㷨2,ɭFĹ鲢,ѡ̱߽й鲢,ƳCOST(T)COST(MST).
2.1㷨STִ,֧TΪһMST,ҽ㷨,δκSteiner㣻ֻҪMSTMRSTĽ,㷨STȻҵһSteiner,ʹCOST(T)COST(MST).
,֤.
2.1.r=COST(T)/COST(MST),2/3r1.
֤:MRSTĶ,COST(T)COST(MRST).֪COST(MST)3/2COST(MRST),

2.2.COST(T)/COST(MRST)<3/2.
֤:Ըn,COST(T)<COST(MST),

,2.2,COST(T)/COST(MRST)=1<3/2.
2.3.ST㷨ʱ临ΪO(n2).
֤:Ȼ,ST㷨,(1.1)ĲΪO(n2),Ҳ(1.2)(1.4)ĲΪO(n).Ϊٲ2ʱ临,ǻڲ1Ŀʼ,Zеÿһv,vZ-{v}ӱ.ÿһʱ,ʱӱ.ʹ,1ʱ临ΪO(n2).
ڲ2,ڲ1еļ,ǿO(n)ʱҳ̱.Ȼ,O(1)ʱĹ鲢.Ϊÿ߿3ʾ,ÿ̱ߺLеıΪO(n),ʶԹ鲢̱ʱ,ҲO(n)ʱ.,2һѭO(n)ʱ.O(n)ѭ,ʲ2ʱ临ΪO(n2).
Steinerĸᳬn,ıΪO(n),Բ3ʱ临ΪO(n).
,֤.
㷨ף6ݵ㷨ԼO(n).
3
ĸһMRSTµĽ㷨,Ľ,㷨µĽƱϸС3/2,ҾнϺõʱ临.н,֧ķ,ƽ㷨ֵ0.8%,ʧΪһʵ㷨.Suyder,㷨޸,ʺάͶάManhattanռMRST.㷨еҪΪȡСֵ,㷨Ҳǳڲֲʽʵ֣8.

л߶Գ븴ʦĽԵ޸л.
Ŀоõ863߿ƼĿ(No.863-306-ZT06-01-4).
߼飺,1956,ʿ,,ҪоΪ㷨,˹,м.
,1975,˶ʿ,ҪоΪݿ,㷨.
ܺ,1938,,ʿʦ,ҪоΪ㷨,˹.
ߵλ(ɽѧѧϵϡ250100)
(ɽѧѧϵϡ250100)
ܺ(ɽѧѧϵϡ250100)
οף
1Hwang F K,Richards D S,Winter P.The Steiner Tree Problem.The Netherlands:North-Holland,1992.20200
2Maxemchuk N F.Video distribution on multicast networks.IEEE Journal on Selected Areas in Communications,1997,15(3):357372
3Hanan M.On Steiner's problem with rectilinear distance.Journal on Applied Mathematics,1966,14(6):255265
4Synder T L.A simple and faster algorithm for the rectilinear Steiner problem in general dimension.In:Ravi R ed.Proceedings of the ACM Symposium on Computational Geometry.New York:ACM Press,1990.13401345
5Kahng A B,Robins G.A new class of iterative Steiner tree heuristics with good performance.IEEE Transactions on Computer Aided Design,1992,11(7):893902
6Salowe J S,Warme D M.An exact rectilinear Steiner tree algorithm.In:Yao Y Y ed.Proceedings of the IEEE International Conference on Computer Design.Cambridge,MA:IEEE Press,1993.472475
7Aho A V,Hopcroft J E,Ullman J D.The Design and Analysis of Computer Algorithms.Reading,MA:Addison-Wesley Publishing Company,1975.172176
8Ma Jun,Takaoka T,Ma Shao-han.Parallel algorithms for a class of graph theoretic problems.Transactions of Information Processing Society of Japan,1994,35(7):12351240
ոڣ1998-08-31
޸ڣ1999-03-03
