Tamanho da fonte:
Implementação do Algoritmo de Christofides para o Problema de Ciclos e Caminhos Hamiltonianos em Grafos de Kneser
Última alteração: 2012-11-22
Resumo
- Introdução: Um dos problemas mais classicos da computação é o problema do Caixeiro Viajante. Nele um comerciante deve viajar entre cidades, da forma menos custosa possivel, sem passar duas vezes na mesma cidade e no final retornar para a cidade de origem. Um problema semelhante descrito por Hamilton consiste em: Dado um grafo G decidir se ele contem um circuito Hamiltoniano (um circuito que passa por todos os vértices exatamente uma vez, com excessão do primeiro). Neste trabalho desejamos transformar o problema do circuito Hamiltoniano em grafos de Kneser em uma instância do problema do Caixeiro Viajante métrico, aplicar o algoritmo de aproximação de Christofides, e usar a solução encontrada como uma solução do problema inicial.
- Metodologia: Estudamos os conceitos de teoria dos grafos pertinentes ao problema do caixeiro viajante e de circuitos Hamiltonianos atraves de leitura da bibliografia e reuniões como orientador. Estudamos e implementamos os passos do algoritmo de Christofides como algoritmos individuais.
- Objetivos: Inicialmente desenvolver um algoritmo que achasse\poucos" caminhos vertice-disjuntos que cobrem todo o grafo. Posteriormente resolvemos apenas nos focar nos estudos tanto dos problemas quanto das soluções que estão envolvidos no algoritmo de Christofides.
- Resultados: Não conseguimos alcancar a meta inicial devido a um problema na nossa estrategia inical, porém o estudo dos problemas que estão envolvidos no algoritmo de Christofides foram concluidos e foram essenciais para um aprofundamento no tema.
- Conclusão: A busca por uma prova, uma contra prova ou apenas por um reforco da conjecturade Lovasz continua a incitar importantes estudos em teoria dos grafos e o algoritmo de Christofides continua a ser uma peca em potencial desse quebra-cabeças.