Learning Automata-Based Algorithms for Solving Stochastic Minimum Spanning Tree Problem

Download Now Date Added: Mar 2011
Format: PDF

Due to the hardness of solving the Minimum Spanning Tree (MST) problem in stochastic environments, the Stochastic MST (SMST) problem has not received the attention it merits, specifically when the Probability Distribution Function (PDF) of the edge weight is not a priori known. In this paper, the authors first propose a learning automata-based sampling algorithm to solve the MST problem in stochastic graphs where the PDF of the edge weight is assumed to be unknown. At each stage of the proposed algorithm, a set of learning automata is randomly activated and determines the graph edges that must be sampled in that stage. As the proposed algorithm proceeds, the sampling process focuses on the spanning tree with the minimum expected weight.