Neste trabalho, vocês vão praticar soluções para o problema do caixeiro viajante, através de heurísticas.

3 pessoas, as mesmas do TP1.

Comece a fazer imediatamente. Você nunca terá tanto tempo quanto agora! :)

A submissão deve ser feita pelo SGA, até o dia 5 de Abril de 2015, às 23:59 horas. Trabalhos após esta data não serão aceitos. Esta data não será modificada.

A documentação deve ser entregue impressa no dia da apresentação. Ela deve estar no formato de artigo da SBC (pesquise na web o formato e confira comigo em sala). A documentação também vale ponto! Ou seja, vocês não vão tirar total, caso não entreguem a documentação. A documentação deve conter, com suas palavras: 1) Introdução (falar sobre o trabalho)2) Objetivo (dizer o objetivo do trabalho)3) Complexidade (discutir a complexidade da(s) solução(ões) através da

apresentação e comentário de uma tabela, como a seguir. Compare o desempenho em termos de tempo de execução dos grafos selecionados do TSPLIB. Determine o tempo necessário para executar cada algoritmo em cada um dos casos). Você deve escolher 5 grafos entre os apresentados no link: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/

4) Conclusão (descrever o que fizeram, o que foi fácil e o que foi difícil de fazer)

Este trabalho será corrigido em sala (aula no laboratório). Isto significa que, além de entregar pelo SGA, na aula seguinte você deve apresentá-lo pessoalmente. Trabalhos entregues no SGA, mas não apresentados, não serão considerados. Saiba que a correção será realizada no dia da apresentação, com base na seleção do arquivos de entrada (grafos do TSPLIB) que serão compartilhados.

Algoritmo brg180.tsp.gz d1655.tsp.gz eil51.tsp.gz gr17.tsp.gz p654.tsp.gz

Heurística 1

12 segundos 1233 segundos

4 segundos 90 segundos 32 segundos

Heurística 2

1234 segundos

1234 segundos

1234 segundos

1234 segundos

1234 segundos

Heurística 3

54356,03 segundos

54356,03 segundos

54356,03 segundos

54356,03 segundos

54356,03 segundos

� de �1 2

TP2: Caixeiro Viajante Profa. Anna Izabel Tostes

Objetivo

Modalidade

Dica

Submissão

Documentação

Correção

Você pode (e deve) utilizar os dias entre a entrega no SGA e a data de apresentação para aperfeiçoar seu trabalho, caso precise de mais tempo. Contudo, a entrega no SGA deve ter 90% do trabalho pronto. Ou seja, se você entregou um trabalho que não tem todos os algoritmos pedidos, e no dia da apresentação milagrosamente chegou com o trabalho pronto, não será considerado. Apenas serão avaliados os algoritmos para os tópicos que você já postou no SGA (em outras palavras, pequenas correções podem ser feitas nesse intervalo de tempo, mas não criação do algoritmo do zero!).

Você deve propor a melhor heurística que conseguir pensar (e implementar) para o problema do caixeiro viajante (simétrico): "Given a set of n nodes and distances for each pair of nodes, find a roundtrip of minimal total length visiting each node exactly once. The distance from node i to node j is the same as from node j to node i."

O seu programa deve gerar um arquivo de saída, imprimindo os resultados de cada grafo exigido no dia da apresentação. Por exemplo, suponha para a seguinte lista de grafos:

Então, o arquivo de saída deve conter os tempos de execução para cada grafo:

Esses tempos são os melhores obtidos para esses problemas. Veja a lista completa em: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html Se você fizer melhor que isso (tempo menor), considero 5 pontos extras no total. Observação: você precisa gerar esse arquivo de saída! Tem que ser arquivo de saída. Não é impresso na tela, ok?

� de �2 2

Descrição

a280ali535att48att532

Lista impressa de grafos

2579 202339 1062827686

Arquivo de saída