
COMPUTER ENGINEERING
1999 25 8 Vol.25 No.8 1999



ڽ滮Steiner Tree 
Σϯԣ
ժҪڽ滮Steiner Tree ·ͨԭʽ㷨Ľ˽㷨Чʣ֤˽滮㷨Чԡ
ؼʣSteiner Tree滮NP-complete
Solve Steiner Tree Problem Based on Evolutionary Programming
Qu Runtao,Xi Yugeng,Han Bing
(Dept. of Automation,Shanghai Jiaotong University,Shanghai 200030)
AbstractIn this paper a novel method based on evolutionary programming is proposed to solve the Steiner Tree Problem,we combined with the heuristic alogoithm to improve the efficient of the evolutionary algorithm. The effective of evolutionary programming alogrithm is given out through simulation.
Key wordsSteiner TreeEvolutionary programmingNP-complete
Steiner Tree [1]ͼеһ NP-complete ⣬й㷺Ӧ [2] ܵӡ 
Steiner Tree  [1]  
һԱʾΪͼ G  (V  E  C)  V Ƕļϣ N 㣻 E Ǳߵļϣ L ߣ C ǱߵĴۣ c:E  R  ci,j ʾ i  j ֮Ĵۡ Steiner Tree Ǹһļ D V £Ѱ G һ S=(V'  E')  D еж㣬 V' V  E' E ʹ Cost(S)=  c(e) С 
 Steiner Tree Ƚϼ򵥣ǳѣͼһͨʽһ⡣ʽĽŻʱҪѰµķһ⡣ 
㷨ǽ NP-complete һЧԣںܶ NP-complete ϵõӦãΪ͵ǻŴ㷨⡣ĿǰѾ [3] ʹŴ㷨 Steiner Tree ⣬ȫʹŴ㷨 Steiner Tree ЧʱȽϵ£˱ͼͨ滮㷨ʽ㷨 Steiner Tree ⡣ 
1 Steiner ʽ㷨ʵ 
ĿǰѾкܶ Steiner ʽ㷨 [2] Щ㷨ֻܵõ Steiner Ľƽ⣬õ MST ʽ㷨 
 Steiner  MST 㷨ͨʵ֡һ G(V  E) һڵ D  V ȴ G һͼ G'  G' ֻ D еĽڵ㣬ͼнڵ㼯 D еĽڵͨС·ӣȻ G' Сչ G' еıӳ G õ Steiner Ӧָǣͨ MST õ Steiner Żģоָ MST 㷨Žһ룬ƽϷǳӽšͼ 1 һ򵥵ģͣͼ 2 ʹ MST 㷨 Steiner Tree Ľ⣬ͼ 3 ŵ Steiner Tree Ľ⡣

ͼ 1 ģ 

ͼ 2 ʹ MST 㷨Steiner Tree Ľ

ͼ 3 ŵ Steiner Tree Ľ
Steiner Tree ʵѰе Steiner 㣬 Steiner Ĵڣʹͨ Steiner ĿĽڵĴۼСвĿĽڵеĽڵ㶼ܳΪ Steiner 㡣ͬ Steiner ϵõͬĽڵĿ V  =N ĿĽڵĿΪ D  =M ĿΪ C0N-M+C1N-M+C2N-M+A+CN-MN-M=2N-Mɼ Steiner Tree  NM ָһ NP ⡣ 
2 滮㷨 
滮 [4]  L.J.Fogel,A.J.Owens  M.J.Walsh  D.B.Fogel Ƶһ㷨ģеȻѡƣͨȺڽռнŵ滮㷨в㷨ƣرʺڽͳԽĵ⡣Ϊ [5]  
Step1: ɴżʼȺ壻 
Step2: Ⱥиָ꣬ 
Step3: ֹͣ 
(1) ѡȡָǰ 50 帴Ƶһ 
(2) ѡĸ尴һһ 
(3) ϲ (1)  (2) γһȺ壬ص 2  
滮Ŵ㷨һнϺõȫܣвͬĲص㡣Ŵ㷨ǿŴܵĸĽҪͨ滮ȺεĽܵĸĽҪͨ졣֮Ĳͬǵ÷ΧһؽŴ㷨ŻܽϺã滮ܽϺáڱĵҪĿ֤ʹý㷨 Steiner Tree Ŀԣȡ Steiner Tree Ž⣬˱ʹ˲Լ򵥵Ľ滮㷨ͬҲʹŴ㷨ͬķ Steiner Tree ⡣ 
3 ڽ滮ʽ㷨 Steiner Tree  
 [3] Ŵ㷨ͨչб룬չķΧڶŻ Steiner Tree ÷һִ㷨Чʺܵ͡ϽڵķԿ Steiner Tree ıһŻ⣬ɷֽΪʵ֣ѡ Steiner 㣬Ȼͨʽ㷨ڸ Steiner µ Steiner Tree ˱Ŀǽ㷨ʽ㷨 Steiner Tree ⡣Ľ滮㷨 MST ʽ㷨ͬ˼ͷҲƹ㵽 Steiner ʽ㷨 
ʹý滮㷨ѡ Steiner 㣬Ȼѡѡ Steiner 㣬ʹʽ㷨Щѡ Steiner µ Steiner ڽ滮㷨еÿһӦһ Steiner ͨ滮㷨ıѡʹ𲽽Ż Steiner Tree Ľ⡣ 
㷨ľϸ£ (1)   MODE[N] һάʾ壬 MODE[i]=0  1  D еĵ MODE[i]=1 ڲ D еĵ㣬 MODE[i]=1 ѡõΪ Steiner 㣻 MODE[i]=0  (2) ӦȺȷ ʹʽ㷨 Steiner ΪӦȺ (3)  ͨѡĲ D еĵ㣬 MODE[i] ȡԸб졣ķȺĹģйأڽĿʼʹýϴıȣڽĺڲýСıȡ (4) ѡ Բһ滮ѡԣΪ˱ָĲ죬ֹȺھֲСֵĲ˶ͬĸ屣һĲԡڽÿһ Cmax ΪȺеֵͬĸ壬һ壬Ĵ޸Ϊ Ci =Ci +Cmax ݽ滮ѡÿһӺõУȻѡ 50 ĸŴһͬĸһ֣ȺĶԣ˹ (5) ־ѡ 㷨Ľ־ַʽһǸӦĿ꺯ֵѴﵽֵһʹõпơڱ㷨Ŀ֤㷨ЧԣȡŽ⣬˱ʹõƽ㷨Ľ 
4 ʵ 
Ϊ֤ĽʹķʵԵͼģ [2]  N ڵһڵľʹŷ롣ڵ i  j ֮ıߣݽڵ֮ľ밴һĸʲ߲ĸʰĹʽ 

ʽУ d(i,j)  i  j ֮ľ룬 L ڵ룬     (0,1] ֮Ĳ  ʱߵܶ󣬵  СʱСıھıߵܶߵĴ۵ڵľ롣 
 10  25 ڵģϽ滮㷨õĽͻʽ㷨Ľ˶Աȡڷн滮㷨 50 ȺģѡΪ 20 ѡΪ 4  1 ͼ 4 ʵ߸ʽ㷨ͽ滮㷨ܱȣ߸ʽ㷨Żıȣ 20 ηƽֵͼ 4 Կʹý滮㷨õĽӽŻ Steiner Ľ⡣ΪҪǣʽ㷨õĽǲȶģ [5] ֤£ʹ MST ʽ㷨õĽŽһʹý滮ʽ㷨ϵķ Steiner ⣬ʽ㷨³ԣȻڸһ۵ǰ»õġ 

ͼ 4  
5 
ʹý滮㷨ʽ Steiner Tree ˼·ַܱ֤ŵĽ⣬ܹʽ㷨ܣʽ³ԣַЧġ 
ߵλϺͨѧԶоϺ 200030
ο
1 Winter,P.Steiner Problem in Networks: A Survey.Networks,1986, 17(1)  129-167 
2 Bernard M W.Routing of Multipoint Connections.IEEE JSAC, 1988,6(4)  1617-1621 
3 Julstrom BA.A Genetic Algorithm for the Rectilinear Steiner Problem. Proc. of the 15'th International Conference on Genetic Algorithms. University of Illinois at Urbana-Champaign Morgan Kaufmann,San Mateo, CA,1993-07  474-479 
4 ¹ . Ŵ㷨Ӧ . ʵ ,1996 
5 Kou L,Markowsky G,Berman L.A fast Algorithm for Steiner Trees, Acta Informatica,1981,15  141-145 
