Heurística aplicada ao problema árvore de Steiner Euclidiano com representação nó-profundidade-grau
Carregando...
Data
2014-09-03
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
A variation of the Beasley (1992) algorithm for the Euclidean Steiner tree problem
is presented. This variation uses the Node-Depth-Degree Encoding, which requires an
average time of O(n) in operations to generate and manipulate spanning forests. For
spanning tree problems, this representation has linear time complexity when applied to
network design problems with evolutionary algorithms. Computational results are given
for test cases involving instances up to 500 vertices. These results demonstrate the use of
the Node-Depth-Degree in an exact heuristic, and this suggests the possibility of using
this representation in other techniques besides evolutionary algorithms. An empirical
comparative and complexity analysis between the proposed algorithm and a conventional
representation indicates the efficiency advantages of the solution found.
Descrição
Citação
OLIVEIRA, M. A. A. Heurística aplicada ao problema árvore de Steiner Euclidiano com representação nó-profundidade-grau. 2014. 76 f. Dissertação (Mestrado em Ciência da Computação)–Universidade Federal de Goiás, Goiânia, 2014.