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

CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
PROJETO E ANÁLISE DE ALGORITMOS

Última alteração: Julho 16, 2002

Referências PCV Assimétrico

Horario : Terça: 14:55 - 16:35, Quinta: 14:55 - 16:35, Sala: 2029
Professor: Nivio Ziviani
Monitora: Claudine Santos Badue
2$^{\underline{o}}$ Trabalho Prático - 02/07/02 - 10 pontos
Data de Entrega: 26/07/02
Penalização por Atraso: 1 ponto até 30/07/02 mais 1 ponto por dia a seguir
Observação: Toda a documentação deverá ser apresentada como uma página acessível via Web (apresente o link para acesso à documentação).
Ponto extra: Trabalhos entregues completo até 16/07/02.

• Apresente pelo menos um exemplo prático (e não mais do que três) que possa ser modelado através dos seguintes problemas:
  • ciclo de hamilton
  • Conjunto independente de vértices
  • Clique
  • Coloração de grafos
  • Problema do caixeiro viajante
  • Satisfabilidade

  
  

• 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.
  • Apresente uma análise indicando o quanto a solução heurística fornecida aproxima-se do resultado ótimo (voce pode explicar resultados encontrados na literatura ou ainda apresentar sua própria demonstração).
  • Realize testes com entradas escolhidas aleatoriamente e compare os resultados com a análise de eficiência apresentada no item anterior. Comente os resultados obtidos e discuta o quão próxima a análise teórica está da realidade.
  • 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: [CLR], [HS], [GJ], [L], [S]