Cellular SDS Algorithm for the Rectilinear Steiner Minimum Tree

The rectilinear Steiner minimum tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance which has extensive applications in real world and is known to be NP-complete. Because of the intrinsic characteristic of the hard computability, this problem cannot be solved accurately by efficient algorithms up to now. The stochastic diffusion search algorithm is a newly population-based algorithm whose operating mechanism is quite different from ordinary intelligent algorithms, so bring it with special advantage in solving some optimization problems. By carefully studied the stochastic diffusion search algorithm we designed a cellular automata stochastic diffusion search algorithm for the rectilinear Steiner minimum tree problem that has low time complexity. Experimental evidence is presented which demonstrates that the algorithm also works well in practice even for large scale rectilinear Steiner minimum tree.