Repositório Institucional da UFPB
Use este identificador para citar ou linkar para este item:
https://repositorio.ufpb.br/jspui/handle/tede/6140| Tipo: | Dissertação |
| Título: | Métodos heurísticos aplicados ao problema da árvore de Steiner rectilinear |
| Autor(es): | Silva, Thiago Gouveia da |
| Primeiro Orientador: | Cabral, Lucídio dos Anjos Formiga |
| Resumo: | Este trabalho apresenta uma nova heurística, denominada Heurística 1, e a implementação das metaheurísticas GRASP, Simulated Annealing e Algoritmos Genéticos para o problema da árvore retilínea mínima de Steiner (RSMTP), discorrendo sobre seus aspectos teóricos, como a complexidade computacional; e práticos, como pseudocódigos e estratégias de implementação. As novas abordagens para o RSMTP apresentadas, em especial os Algoritmos Genéticos, ostentam resultados computacionais de qualidade superior às apresentadas pelas melhores heurísticas da literatura atual. |
| Abstract: | This work presents a new heuristic, called Heurística 1, and the implementations of the GRASP, Simulated Annealing and Genetic Algorithms metaheuristics for the rectilinear Steiner minimum tree problem (RSMTP), talking about its theoretical aspects, like computational complexity, and practical ones, like pseudo-codes and implementation strategies. The new techniques for RSMTP presented, especially the Genetic Algorithms, have computational results of superior quality in comparison to the best heuristics in present litera |
| Palavras-chave: | Árvores Retilíneas de Steiner Metaheurística Simulated Annealing GRASP Algoritmos Genéticos Rectilinear Steiner Trees Metaheuristic Simulated Annealing GRASP Genetic Algorithms |
| CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | BR |
| Editor: | Universidade Federal da Paraíba |
| Sigla da Instituição: | UFPB |
| Departamento: | Informática |
| Programa: | Programa de Pós Graduação em Informática |
| Citação: | SILVA, Thiago Gouveia da. Métodos heurísticos aplicados ao problema da árvore de Steiner rectilinear. 2009. 108 f. Dissertação (Mestrado em Informática) - Universidade Federal da Paraíba, João Pessoa, 2009. |
| Tipo de Acesso: | Acesso aberto |
| URI: | https://repositorio.ufpb.br/jspui/handle/tede/6140 |
| Data do documento: | 28-Ago-2009 |
| Aparece nas coleções: | Centro de Informática (CI) - Programa de Pós-Graduação em Informática |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| Arquivototal.pdf | 3,38 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.