Problemas NP Completo

UNIVERSIDADE FEDERAL DO AMAZONAS
INSTITUTO DE COMPUTAÇÃO
MESTRADO EM INFORMÁTICA

Projeto e Análise de Algoritmo - PAA
Segundo Trabalho Prático

Aluno: Carlos Alberto da Costa Barata

Universidade Federal do Amazonas
Mestrado em Informática
Projeto e Análise de Algoritmos
Professor: Edleno Silva de Moura
2° Trabalho Prático - 1° Semestre de 2013
Sumário
Problema caxeiro viajante (PCV) ...................................................................................... 2
Problema de decisão do bin packing ................................................................................ 4
Problema de decisão da coloração de mapas com três cores..................................... 8
Problema de decisão do clique ....................................................................................... 10
Problema de decisão da mochila .................................................................................... 12
Problema de decisão da cobertura de conjuntos ......................................................... 14
Problema de decisão da cobertura de vértices............................................................. 16
Problema de decisão da soma de subconjuntos .......................................................... 17
Problema da soma de subconjuntos - programação dinâmica .................................. 19
Referências ......................................................................................................................... 21

Página:1

Problema caxeiro viajante (PCV)
Suponha que um caixeiro viajante deseja visitar N cidades de certa localização e que entre alguns pares de cidades existem rotas, através das quais ele pode viajar de uma cidade para outra. Cada rota tem um número associado que pode representar a distância ou o custo necessário para percorrê-la. Assim, o caixeiro viajante deseja encontrar um caminho que passe por cada uma das N cidades apenas uma vez, e, além disso, que tenha um