6898 Algoritmos em Grafos

Trabalho / Problema do caixeiro viajante

Introdução

O objetivo deste trabalho é a implementação de algoritmos heurísticos para o problema do caixeiro viajante.

O trabalho é em equipe de até 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.

Descrição

O programa deve receber dois parâmetros na linha de comando. O primeiro parâmetro é o nome do algoritmo e o segundo é o arquivo do grafo. O programa deve executar o algoritmo para o grafo e escrever na saída padrão o resultado da execução do algoritmo.

Os seguintes algoritmos devem ser implementados:

tsp-nn: Algoritmo vizinho mais próximo.

tsp-mst: Algoritmo baseado na árvore geradora mínima.

tsp-nn-2opt: Algoritmo 2-opt aplicado a solução gerada pelo algoritmo tsp-nn.

tsp-mst-2opt: Algoritmo 2-opt aplicado a solução gerada pelo algoritmo tsp-mst.

tsp-nn-3opt (extra): Algoritmo 3-opt aplicado a solução gerada pelo algoritmo tsp-nn.

Formato da entrada e saída para o TSP

A entrada é um arquivo que contém a descrição de um grafo não orientado completo. As entradas 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):

n-int x-real y-real

O valor n-int é o número do vértice, os valores x-real e y-real correspondem a coordenada $(x, y)$ do vértice. O grafo (completo) de entrada deve ser construído calculando a distância entre todos os pares de pontos. Para dois vértices $(x_1, y_1)$ e $(x_2, y_2)$ 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.

A saída consiste do custo da viagem (primeira linha) e dos vértices (um por linha) da viagem encontrada. Por exemplo, a saída para a viagem 2 1 4 3 2 com custo 13, deve ser

13
2
1
4
3
2

Desenvolvimento

Para facilitar o desenvolvimento do trabalho, está disponível um “projeto” com os arquivos iniciais de código, um programa testador e um Makefile para compilar, testar e enviar o programa.

Para fazer o download e utilizar este projeto é necessário ter os seguintes programas instalados: git, make e python2.7. No Ubuntu ou Debian estes programas podem ser instalados com o comando

apt-get install git make python2.7

Para fazer o download do projeto, execute o comando

git clone http://malbarbo.pro.br/git/tsp

Após a execução deste comando, um diretório chamado tsp terá sido criado. No diretório tsp/src existe um diretório para cada linguagem que pode ser utilizada para implementar o trabalho, você deve usar o comando

chmod -f +x src/lang/{run,build}

para avisar o testador sobre a linguagem que será utilizada. Observe que você deve trocar a palavra lang pelo diretório da linguagem escolhida.

Todos os arquivos de código devem ficar no diretório src/lang/. Além disso, já existe um arquivo principal, onde a função principal do seu programa deve ser definida.

Linguagens

O trabalho pode ser implementado em uma das seguintes linguagens:

• C (compilador gcc 4.8)
• C++ (compilador g++ 4.8)
• Java (compilador/interpretador openjdk 1.7)
• Pascal (compilador freepascal 2.6)
• Python (interpretador padrão versão 2.7 ou 3.3)

Atenção: Só é permitido a utilização das bibliotecas padrão de cada linguagem/ambiente.

Testes

Para executar os testes, entre no diretório tsp e execute um dos comandos

make testar         # testar todos os algoritmos
make testar-nn      # testar a implementação do algoritmo tsp-nn e tsp-nn-2opt
make testar-mst     # testar a implementação do algoritmo tsp-mst e tsp-mst-2opt
make testar-desafio # testar a implementação do algoritmo tsp-nn-3opt

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.

Após enviar o trabalho, o aluno deverá entrar na página da disciplina (o endereço será impresso na tela depois do envio), imprimir e assinar o termo de autoria. O termo de autoria é um documento em que o aluno afirma que ele é o autor do código do trabalho que ele enviou e que portanto, não copiou parte significativa do programa de outra pessoa ou da internet.

Avaliação

O trabalho será avaliado de acordo com os critérios:

• Corretude e completude: o programa tem quer passar em todos os testes.
• Tempo de execução: as implementações devem ter o mesmo tempo de execução dos algoritmos estudados em sala.
• Semelhança com o pseudocódigo: o código deve ser semelhante ao pseudocódigo dos algoritmos estudados em sala.
• Clareza lógica: a lógica nos programas deve ser clara.
• Boas práticas de programação: o código deve estar bem escrito e organizado, não deve haver código repetido.

Atividade extra

Quem implementar o algoritmo tsp-nn-3opt ganha 1,0 ponto extra na nota da prova.

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 (com vértices repetidos)
• Utilize o algoritmo de Prim para encontrar a árvore geradora mínima
• Implemente a fila de prioridades usado pela algoritmo de Prim usando busca linear
• Na implementação do 2-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, após descobrir a melhor troca, construa uma nova viagem com troca ao invés de alterar a viagem atual (a implementação é mais simples)