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.
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.
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 3Os 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
1A 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-realO 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
2Para 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.7Para fazer o download do projeto, execute o comando
git clone http://malbarbo.pro.br/git/graphardApó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.
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.
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 TSPPara enviar o trabalho, execute o comando
make enviarO 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.
O trabalho será avaliado de acordo com os critérios:
Esta seção contém alguns dicas de implementação. Use as que achar útil.
EC
TSP