Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados III

2$^o$ semestre de 2008

Trabalho prático 3

Data de entrega: 27 de outubro de 2008

Este trabalho prático tem por objetivo avaliar experimentalmente a qualidade de algoritmos aproximados, em particular a estratégia de Christofides para o problema de caixeiro viajante.

Pede-se:

1. Implemente a estratégia de Christofides. O seu programa deve ser capaz de ler bases de dados no formato TSPLIB.

2. Avalie experimentalmente a razão de aproximação do algoritmo usando bases de dados da TSPLIB. Para os casos onde não haja solução ótima conhecida, considere a melhor solução obtida até o momento como ótima.

3. Apresente a documentação das implementações realizadas (veja aqui maiores detalhes sobre a entrega de trabalhos práticos).
   

4. (Pontos extras) Paralelize o programa implementado.