Trabalho Prático 2 de Algoritmos 2

Tecnologias

• Python3

Resumo

Este trabalho apresenta a implementação e análise de três estratégias para resolver o Problema do Caixeiro Viajante Euclidiano, com foco em um método exato e dois algoritmos heurísticos. A pesquisa explora o algoritmo Branch-And-Bound, uma abordagem exata que busca a solução ótima, mas com alta complexidade no tempo de execução e elevado consumo de memória, especialmente para instâncias grandes. Além disso, são abordados dois algoritmos heurísticos: Twice-Around-The-Tree e o algoritmo de Christofides, ambos oferecendo soluções aproximadas com fatores de aproximação de 2 e 1,5, respectivamente. Os resultados experimentais evidenciam que, enquanto o \textit{Branch-And-Bound} oferece uma solução exata, sua viabilidade é limitada em termos de tempo para instâncias grandes, enquanto os algoritmos heurísticos, se destacam pela eficiência em tempo. A escolha do algoritmo mais adequado depende das prioridades do problema, como a precisão ou a eficiência temporal.

Clique no ícone acima para acessar o relatório em PDF.

Responsáveis

Déborah Yamamoto

Caroline Carvalho