上海交通大学学报（英文版） ›› 2011, Vol. 16 ›› Issue (6): 734-741.doi: 10.1007/s12204-011-1218-0
Solving the Euclidean Steiner Minimum Tree Using Cellular
Stochastic Diffusion Search Algorithm
ZHANG Jin (张 瑾), ZHAO Ya-liang (赵雅靓), MA Liang (马 良)
- (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)
Solving the Euclidean Steiner Minimum Tree Using Cellular
Stochastic Diffusion Search Algorithm
ZHANG Jin (张 瑾), ZHAO Ya-liang (赵雅靓), MA Liang (马 良)
- (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)
摘要： 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.
中图分类号: