Submitted by Luanna Matias (lua_matias@yahoo.com.br) on 2015-02-06T19:23:12Z
No. of bitstreams: 2
Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-02-19T14:34:20Z (GMT) No. of bitstreams: 2
Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-02-19T14:34:20Z (GMT). No. of bitstreams: 2
Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf: 1092566 bytes, checksum: 55edbdaf5b3ac84fe3f6835682fe2a13 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2014-09-03 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / 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. / É apresentada uma variação do algoritmo de Beasley (1992) para o Problema árvore de Steiner Euclidiano. Essa variação utiliza a Representação Nó-Profundidade-Grau que requer, em média, tempo O(n) em operações para gerar e manipular florestas geradoras. Para problemas de árvore geradora essa representação possui complexidade de tempo linear sendo aplicada em problemas de projeto de redes com algoritmos evolutivos. Resultados computacionais são dados para casos de teste envolvendo instâncias de até 500 vértices. Esses resultados demonstram a utilização da representação Nó-Profundidade-Grau em uma heurística exata, e isso sugere a possibilidade de utilização dessa representação em outras técnicas além de algoritmos evolutivos. Um comparativo empírico e da análise de complexidade entre o algoritmo proposto e uma representação convencional indica vantagens na eficiência da solução encontrada.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/4171 |
| Date | 03 September 2014 |
| Creators | Oliveira, Marcos Antônio Almeida de |
| Contributors | Soares, Telma Woerle de Lima, Foulds, Leslie Richards, Soares, Telma Woerle de Lima, Foulds, Leslie Richard, Delbem, Alexandre Cláudio Botazzo, Coelho, Érika Morais Martins |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, -862078257083325301, -961409807440757778 |
Page generated in 0.0019 seconds