Trabalho / Ciclos eulerianos e o problema do caixeiro viajante

Introdução

O objetivo deste trabalho é a implementação do algoritmo de Hierholzer para encontrar ciclos eulerianos e 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.

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

Descrição

Este trabalho consiste na implementação do algoritmo de Hierholzer para encontrar um ciclo euleriano (EC) e diversos algoritmos heurísticos para o problema do caixeiro viajante (TSP).

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:

ec: Algoritmo de Hilerholzer para encontrar ciclo euleriano.

tsp-nn: Algoritmo vizinho mais próximo para o TSP.

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

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.

Formato da entrada e saída para o EC

A entrada para o EC é um grafo não orientado conexo. Você pode assumir que o grafo de entrada é euleriano.

Os grafos de entrada são especificado com arquivos. Os arquivos estão em uma versão simplificado do formato tgf. O arquivo consiste de um conjunto de vértices e um conjunto de arestas. Exemplo:

a
2
verde
4
#
a 2
verde 3
verde 2
2 3

Os conjuntos de vértices e arestas são separados por uma linha com o caractere #. Cada vértice é especificado em uma linha e pode ter qualquer nome (sem espaço). Cada aresta é especificada por um par de vértices separados por espaço. Desta forma, o grafo do exemplo tem o conjunto $\{a, 2, verde, 4\}$ de vértices e o conjunto $\{(a, 2), (verde, 3), (verde, 2), (2, 3)\}$ de arestas.

A saída consiste dos vértices (um por linha) que compõe o ciclo encontrado. Por exemplo, a saída para o ciclo 1 2 3 1 deve ser

1
2
3
1

Formato da entrada e saída para o TSP

A entrada para o TSP é um grafo não orientado completo.

Os grafos de entrada são especificados com arquivos. 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/graphard

Após a execução deste comando, um diretório chamado graphard terá sido criado. No diretório graphard/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:

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

Execução dos testes

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

make testar      # testar todos os algoritmos
make testar-ec   # testar a implementação do algoritmo de Hierholzer
make testar-tsp  # testar a implementação de todos os algoritmos para o TSP

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.

O trabalho deve ser enviado até as 23:00h do dia 16/06/2013. O termo de autoria assinado deve ser entregue pessoalmente ao professor no dia 17/06/2013.

Avaliação

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

Dicas

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

EC

TSP