Heurística aplicada ao problema árvore de Steiner Euclidiano com representação nó-profundidade-grau

• Ano de defesa: 2014
• Autor(a) principal: Oliveira, Marcos Antônio Almeida de
• Orientador(a): Soares, Telma Woerle de Lima
• Banca de defesa: Soares, Telma Woerle de Lima, Foulds, Leslie Richard, Delbem, Alexandre Cláudio Botazzo, Coelho, Érika Morais Martins
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: Árvore de Steiner Euclidiana; Representação nó-profundidade-grau; Heurística
• Palavras-chave em Inglês: Euclidean Steiner Tree Problem; Heuristic algorithm; Node-depth-degree encoding
• Área do conhecimento CNPq: CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/4171

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.