Solving the Minimum Spanning Tree Problem in Stochastic Graphs Using Learning Automata

In this paper, we propose some learning automata-based algorithms to solve the minimum spanning tree problem in stochastic graphs when the probability distribution function of the edge´s weight is unknown. In these algorithms, at each stage a set of learning automata determines which edges to be sampled. This sampling method may result in decreasing unnecessary samples and hence decreasing the running time of algorithms. The proposed algorithm reduces the number of samples needs to be taken by a sample average approximation method from the edges of the stochastic graph. It is shown that by proper choice of the parameter of the proposed algorithms, the probability that the algorithms find the optimal solution can be made as close to unity as possible.