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

Última alteração: 3. Junho 2003

TSLIB: site sobre problemas NP-completo
Enunciado TP2 em Latex

Horario : Terça: 14:55 - 16:35, Quinta: 14:55 - 16:35, Sala: 2029
Professor: Nivio Ziviani
Monitor: Bruno Pôssas
2 $^{\underline{o}}$ Trabalho Prático - 27/05/03 - 10 pontos
Data de Entrega: 14/06/03
Penalização por Atrazo: 1 ponto até 18/05/03 mais 1 ponto por dia útil 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).

  1. Apresente pelo menos um exemplo prático (e não mais do que três) que possa ser modelado através dos seguintes problemas:
    a)
    Bin packing
    b)
    Cobertura de vértices (vertex cover)
    c)
    Mochila (knapsack)
    d)
    Subset sum
    e)
    Problema do caixeiro viajante


  2. 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).

    O que fazer

    f)
    Prove que este problema é $\cal NP$-Completo.

    g)
    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.

    h)
    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.

    i)
    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).

    j)
    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.

    k)
    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 72 - O 6 6
    48 48 72 O - 6 6
    8 8 48 6 6 - O
    8 8 48 6 6 O -

    l)
    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], [Z]


Nivio Ziviani
2003-06-03