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

Página do item simplificado
dc.contributor.advisor-co1Foulds, Leslie Richards
dc.contributor.advisor1Soares, Telma Woerle de Lima
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/6296363436468330eng
dc.contributor.referee1Soares, Telma Woerle de Lima
dc.contributor.referee2Foulds, Leslie Richard
dc.contributor.referee3Delbem, Alexandre Cláudio Botazzo
dc.contributor.referee4Coelho, Érika Morais Martins
dc.creatorOliveira, Marcos Antônio Almeida de
dc.creator.Latteshttp://lattes.cnpq.br/5549176720730189eng
dc.date.accessioned2015-02-19T14:34:20Z
dc.date.issued2014-09-03
dc.description.abstractA 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.eng
dc.description.provenanceSubmitted 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)eng
dc.description.provenanceApproved 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)eng
dc.description.provenanceMade 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-03eng
dc.description.resumoÉ 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.eng
dc.description.sponsorshipFundação de Amparo à Pesquisa do Estado de Goiás - FAPEGeng
dc.formatapplication/pdf*
dc.identifier.citationOLIVEIRA, 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.eng
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/4171
dc.languageporeng
dc.publisherUniversidade Federal de Goiáseng
dc.publisher.countryBrasileng
dc.publisher.departmentInstituto de Informática - INF (RG)eng
dc.publisher.initialsUFGeng
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)eng
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectÁrvore de Steiner Euclidianapor
dc.subjectRepresentação nó-profundidade-graupor
dc.subjectHeurísticapor
dc.subjectEuclidean Steiner Tree Problemeng
dc.subjectHeuristic algorithmeng
dc.subjectNode-depth-degree encodingeng
dc.subject.cnpqCIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAOeng
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/tede/retrieve/16909/Disserta%c3%a7%c3%a3o%20-%20Marcos%20Ant%c3%b4nio%20Almeida%20de%20Oliveira%20-%202014..pdf.jpg*
dc.titleHeurística aplicada ao problema árvore de Steiner Euclidiano com representação nó-profundidade-graueng
dc.title.alternativeHeuristic applied to the Euclidean Steiner tree problem with no-dedepth- degree encodingeng
dc.typeDissertaçãoeng

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertação - Marcos Antônio Almeida de Oliveira - 2014..pdf
Tamanho:
1.04 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)