Desafio
Vence o desafio o grupo que entregar,
em um prazo de 15 minutos,
o circuito de caixeiro viajante de menor custo
para um grafo dado.
Em casos de respostas com custos iguais,
vence o grupo que entregou a resposta primeiro.
Caso um grupo submeta várias respostas,
vale a melhor.
Cada grupo pode ser formado por um ou dois alunos.
Cada aluno só pode submeter respostas com um mesmo grupo.
Pelo menos os três primeiros grupos ganharão pontos na média
(fica a critério do professor premiar outros grupos,
respeitando-se suas classificações).
O grafo é um grafo simples e dirigido,
representado em formato ingênuo:
uma lista de dois elementos,
onde o primeiro é o número de nós no grafo,
e o segundo é a lista de arcos.
Cada arco nessa lista é representado por
uma lista (origem destino custo).
O grafo real terá em torno de 500 nós.
A resposta deverá ser dada como uma lista de nós
na sintaxe de Scheme
(ver exemplo no grafo).
Essa lista
- deverá começar e terminar com 0;
- deve representar um caminho válido no grafo;
- deve incluir todos os nós do grafo
(cada nó pode aparecer múltiplas vezes no caminho).
O custo total da resposta é o somatório dos custos de todos os
arcos implicitamente representados no caminho dado.
Cada grupo deverá usar apenas um computador regular do laboratório.
A máquina poderá ser usado da forma mais conveniente para o grupo;
em particular, cada grupo pode usar um ou mais programas escritos em
uma ou mais linguagens quaisquer.
Os grupos terão um prazo de 30 minutos no laboratório antes do grafo
ser liberado, para configurar suas máquinas.
É vedado o uso de sistemas externos.
As respostas deverão ser enviadas pelo formulário abaixo.
Todos podem
consultar
os custos das respostas já fornecidas.