J Shanghai Jiaotong Univ Sci

Journal of shanghai Jiaotong University (Science) ›› 2011, Vol. 16 ›› Issue (6): 734-741.doi: 10.1007/s12204-011-1218-0

• Articles • Previous Articles     Next Articles

Solving the Euclidean Steiner Minimum Tree Using    Cellular
Stochastic Diffusion Search Algorithm

Solving the Euclidean Steiner Minimum Tree Using    Cellular
Stochastic Diffusion Search Algorithm

ZHANG Jin  (张   瑾),    ZHAO Ya-liang (赵雅靓),    MA Liang  (马   良)   

  1. (1. Institute of Image Processing and Pattern
    Recognition, Henan University, Kaifeng 475001, Henan, China;
    2. School of Management, University of Shanghai for Science and
    Technology, Shanghai 200093, China)
  2. (1. Institute of Image Processing and Pattern
    Recognition, Henan University, Kaifeng 475001, Henan, China;
    2. School of Management, University of Shanghai for Science and
    Technology, Shanghai 200093, China)
  • Received:2010-09-08 Online:2011-12-30 Published:2012-01-12
  • Contact: ZHANG Jin (张 瑾) E-mail:autummoon_1@sina.com

Abstract:  The Euclidean Steiner minimum tree
problem is a classical NP-hard combinatorial optimization problem.
Because of the intrinsic characteristic of the hard computability,
this problem cannot be solved accurately by efficient algorithms up
to now. Due to the extensive applications in real world, it is quite
important to find some heuristics for it. The stochastic diffusion
search algorithm is a newly population-based algorithm whose
operating mechanism is quite different from ordinary intelligent
algorithms, so this algorithm has its own advantage in solving some
optimization problems. This paper has carefully studied the
stochastic diffusion search algorithm and designed a cellular
automata stochastic diffusion search algorithm for the Euclidean
Steiner minimum tree problem which has low time complexity.
Practical results show that the proposed algorithm can find approving results
in short time even for the large scale size, while exact algorithms need to cost several hours.

Key words:

 Euclidean Steiner minimum tree| stochastic
diffusion search| cellular automata

摘要：  The Euclidean Steiner minimum tree
problem is a classical NP-hard combinatorial optimization problem.
Because of the intrinsic characteristic of the hard computability,
this problem cannot be solved accurately by efficient algorithms up
to now. Due to the extensive applications in real world, it is quite
important to find some heuristics for it. The stochastic diffusion
search algorithm is a newly population-based algorithm whose
operating mechanism is quite different from ordinary intelligent
algorithms, so this algorithm has its own advantage in solving some
optimization problems. This paper has carefully studied the
stochastic diffusion search algorithm and designed a cellular
automata stochastic diffusion search algorithm for the Euclidean
Steiner minimum tree problem which has low time complexity.
Practical results show that the proposed algorithm can find approving results
in short time even for the large scale size, while exact algorithms need to cost several hours.

关键词:

 Euclidean Steiner minimum tree| stochastic
diffusion search| cellular automata

CLC Number: