上海交通大学学报（英文版） ›› 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.
中图分类号: