Solving Steiner Tree Problem by Using Learning Automata
Samira Noferesti, Mehri Rajaei · 2009
Dynamic Steiner tree problem (DST) is an important problem that has extensive applications in many areas such as building multicast trees for mobile networks. DST problem is NP-hard, and several approximation algorithms are proposed for finding reasonably good solutions. However, these methods are extensive in terms of times and very sensitive to number of changes in the network. In this paper an iterative algorithm based on learning automata has been proposed for solving DST problem. Experimental results show that our proposed algorithm generates low cost Steiner trees in reasonable running time.