1747 Teoria dos Grafos e Análise dos Algoritmos

Trabalho 3 - Implementação de heurísticas para o problema do caixeiro viajante

Introdução

O objetivo deste trabalho é a implementação de heurísticas para encontrar soluções para o problema do caixeiro viajante (PCV).

O trabalho deve ser feito em equipe de no máximo duas pessoas. O compartilhamento de informações entre as equipes é permitido (e aconselhado), mas o compartilhamento de código não é permitido. Trabalhos que tenham porções significativas de código iguais, ou copiados da internet, serão anulados. Veja a resolução Nº 008/2007-COU para as possíveis sansões disciplinares.

Este trabalho vale 2,0 na segundo nota, 1,0 relativo ao critério de avaliação oficial da disciplina e 1,0 extra (bônus).

Data de entrega: até o dia 12/06/2012 às 23:00h.

Descrição

Implementar as seguintes heurísticas para o PCV:

• Construtivas
  • Vizinho mais próximo (NN)
  • Baseado na árvore geradora mínima (livro do Cormen página 810) (MST)
• Melhorativas
  • 2-Opt
  • 3-Opt

O programa deve receber como parâmetro na linha de comando o nome do algoritmo e o nome de um arquivo e escrever na saída padrão o custo da viagem e a viagem encontrada pelo algoritmo para a instância especificada pelo arquivo de entrada.

O nome do algoritmo pode ser um dos valores: NN, MST, NN+2opt, NN+3opt, MST+2opt, MST+3opt. Nomes do tipo A+B, significam a aplicação da heurística construtiva A seguido da heurística melhorativa B.

Por exemplo, para os parâmetros NN e arquivo.tsp, a saída do programa poderia ser

18 1 2 3 8 6 5 4 7 1

Onde 18 é o custo da viagem e 1 2 3 8 6 5 4 7 1 é a viagem.

Formato do arquivo de entrada

Os arquivo de entrada são uma simplificação dos arquivos da tsplib.

Cada linha do arquivo de entrada contém a descrição de um vértice (ponto no plano cartesiano):

inteiro real real

O primeiro valor é o número do vértice, o segundo a coordenada x e o terceiro a coordenada y. O grafo (completo) de entrada deve ser construído calculando a distância entre todos os pares de pontos. Para dois vértices (x1, y1) e (x2, y2) a distância (inteira) entre os vértices deve ser calculada da seguinte forma:

dx = x1 - x2
dy = y1 - y2
dist_real = sqrt(dx * dx + dy * dy)
dist_int = int(dist_real + 0.5)

Confira as soluções ótimas para estes arquivos de entrada. Observe que estes ótimos foram calculados com distâncias inteiras.

Linguagens

As linguagens permitidas para a implementação deste trabalho são:

• C
• C++
• Java
• Python

Desenvolvimento

Para facilitar o desenvolvimento do trabalho, está disponível um projeto com alguns arquivos iniciais, entre eles um programa chamado runner que compara a execução dos diversos algoritmos e um Makefile para enviar o trabalho.

Para utilizar o programa runner é necessário escrever dois scripts: um chamado compilar, que quando executado deve compilar o seu programa, e outro chamado executar, que quando executado deve executar o seu programa.

Para executar o programa runner, execute o comando

make run

Todos os arquivos de código do programa devem ficar no diretório src, isto é importante porque o script de envio do trabalho enviará, além dos arquivos compilar e executar, apenas os arquivos deste diretório. Tenha o cuidado de não deixar arquivos compilador no diretório src.

Envio do trabalho

Para enviar o trabalho, execute o comando

make enviar

O script de envio criará um arquivo compactado com os arquivos a serem entregues para correção e enviará para a página do professor.

O trabalho deve ser enviado até as 23:00h do dia 12/06/2012. O trabalho deve ser apresentado pela equipe ao professor no dia 13/06 ou 15/06 no horário da aula.

Avaliação

Este trabalho vale 2,0 pontos na segunda nota. O trabalho será avaliado de acordo com os critérios:

• Corretude e completude: o programa deve calcular soluções viáveis para qualquer instância do problema
• Tempo de execução: as implementações dos algoritmos devem ser eficientes
• Boas práticas de programação: o código deve estar bem escrito e organizado

Dicas

Esta seção contém alguns dicas de implementação. Use as que achar útil.

• Crie uma estrutura (classe) para representar um grafo e outra para representar uma viagem
• Coloque verificações em seu código de maneira que não seja possível criar uma viagem inviável
• Utilize o algoritmo de Prim para encontrar a árvore geradora mínima
• Implemente a fila de prioridades usada pela algoritmo de Prim usando busca linear (veja a implementação do algoritmo de Dijkstra feito em sala de aula)
• Na implementação do 2-opt e do 3-opt, para avaliar o custo de uma troca, não é necessário criar uma nova viagem, basta subtrair os custos das arestas removidas e somar o custo das arestas adicionadas
• Na implementação do 2-opt e do 3-opt, após descobrir a troca que mais melhora a viagem atual, construa uma nova viagem com troca ao invés de alterar a viagem atual (a implementação é mais simples)
• Tenha certeza que o seu programa está funcionando para instâncias pequenas, depois você pode executá-lo para instâncias grandes