Find the minimum spanning tree in random graphs using learning automata
Find the minimum spanning tree in random graphs using learning automata
sayyedeh laily shahmoradi1
1) shahmoradi
IOI Code
:
XYBB-ZHHDB
Publication :
3rd International Conference On Research Science And Technology(3rstconf.com)
Abstract :
In this paper, an algorithm based on learning automata for finding the minimum spanning tree in a random graph (spanning tree with the lowest expected cost) is suggested.It is assumed that the weight distribution function of the edges is not known to have access only to the edges of the sample distribution.The purpose of the minimum spanning tree algorithm edges of the graph is the minimum sampling.In the proposed algorithm in each learning automaton graph to sampling reluctance of the candidate and The quantitative analysis will be determined based on whether the limb should be sampled or not.Learning Automata with an appropriate choice of parameters, with the possibility of minimum spanning tree algorithm is able to find a close one.To evaluate the proposed algorithm, the number of samples taken by the algorithm, the number of samples required standard sampling method.The results showed that the samples taken by the proposed algorithm is far less than the number of samples is standard sampling.
Keywords : random graph minimum spanning tree learning automata