Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

Última alteração: Julho 16, 2002

Referências PCV Assimétrico

BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO (BCC) E MATEMÁTICA COMPUTACIONAL (BMC)
ALGORITMOS E ESTRUTURAS DE DADOS III
Professores: Nivio Ziviani (BCC) e Wagner Meira Jr (BMC)
Monitores: Robert Pereira Pinto e Fabricio Benevenuto de Souza
Trabalho Prático 2
Data de Entrega: 23-Julho-2002
Observação: Toda a documentação deverá ser apresentada como uma página acessível via Web (apresente o link para acesso à documentação).

Problema: Dados um conjunto de cidades $C=\{c_1, c_2, \cdots, c_n\}$ e uma distância d(c_i,c_j) para cada par de cidades $c_i, c_j \in C$,encontre o ``roteiro'' para todas as cidades em C cujo comprimento total seja o menor possível.

Este problema é conhecido na literatura como o problema do caixeiro viajante (PCV). Uma versão um pouco diferente é o problema do caixeiro viajante assimétrico (PCVA), o qual pode ser descrito como: dados um conjunto de n cidades e distâncias para cada par de cidades, encontre um roteiro de comprimento mínimo visitando cada cidade exatamente uma vez. No caso do PCVA, a distância da cidade i para a cidade j e a distância da cidade j para a cidade i podem ser diferentes.

O que fazer

• Prove que este problema é $\cal NP$-Completo.
• Implemente um algoritmo capaz de obter a solução ótima para este problema. Informe o tamanho do maior problema que você conseguiu obter a solução ótima. Comente o resultado indicando o motivo da limitação e faca uma estimativa do tempo necessário no caso de termos uma entrada 10 vezes maior que a do maior problema que voce resolveu.
• Implemente uma heurística (ou aproximação) que resolva este problema eficientemente e produza ``boas'' soluções sob o ponto de vista prático. Apresente uma análise de complexidade de tempo da sua heurística. Use a matriz disponível aqui. Imprima o caminho obtido e seu custo. As melhores soluções vão ser premiadas com pontos extras. Mais especificamente, as 5 melhores soluções que sejam até 10% piores (em termos do custo do caminho encontrado) que a melhor obtida.
• Submeta eletronicamente a implementação da solução ótima utilizando como entrada de dados a seguinte matriz:

  - 3 5 48 48 8 8

  3 - 3 48 48 8 8

  5 3 - 72 72 48 48

  48 48 74 - O 6 6

  48 48 74 O - 6 6

  8 8 50 6 6 - O

  8 8 50 6 6 O -

• Apresente a documentação das implementações realizadas (veja aqui maiores detalhes sobre instruções para a entrega de trabalhos praticos).

Referências: [L], [CLR], [HS], [GJ], [S]