Problemas NP-completos e
Programação Dinâmica
Profa. Sandra de Amo
BCC- UFU
O que são problemas NPcompletos ?
Classe P
Classe NP
Classe P = problemas cujas respostas são encontradas utilizando
algum algoritmo O(nk)
Classe NP = problemas para os quais “testar se uma determinada
sugestão de resposta é ou não correta” é feito utilizando algum algoritmo
O(nk)
Problema em aberto desde os anos 70:
P = NP ???
Características de um problema NP
Consistem basicamente em:
(1)
(2)
enumerar todas as possiveis soluções (um número exponencial
de possibilidades) e
testar uma por uma se são soluções !
A parte (1) é exponencial O(2n) mas a parte (2) é polinomial
Problemas NP-completos
Problemas de Decisão: resposta é Sim ou Não
Um exemplo de problema de decisão:
Primo(n): n é primo ?
Problema redutível a outro: P1 é redutivel em P2 se
É possivel programar um algoritmo em tempo polinomial que mapeia as entradas de
P1 nas entradas de P2 de modo que inputs positivos de P1 (P1 responde Sim) são
mapeados em inputs positivos de P2 (P2 responde Sim) e inputs negativos de P1
(P1 responde Não) são mapeados em inputs negativos de P2 (P2 responde Não).
Problema NP-completo : é um problema X da classe NP que é mais difícil que qualquer
outro problema desta classe, isto é, qualquer problema da classe NP se reduz a X.
Se existir um algoritmo O(nk) que resolve X então P = NP
Como a conjectura P = NP ainda não foi mostrada, é bem provável que X não seja
solúvel por nenhum algoritmo O(nk)
Classe P
Classe NP
Classe dos problemas NP-completos = os mais “difíceis” da classe NP
Resolvendo um deles com um algoritmo polinomial  P=NP
Como mostrar que um problema é
NP-completo ?
Suponha que P1 seja um problema que já se mostrou ser
NP-completo.
Um destes problemas é o problema SAT (Teorema de
Cook-Lewin)
Seja um problema P2 com complexidade desconhecida.
Se você conseguir uma redução de P1 para P2, então
você terá provado que P2 é NP-completo !!
Exemplos
Alguns problemas da classe P
• Problema da conectividade em grafos
• Problema de encontrar o caminho mais curto ligando
dois vértices em um grafo
• Problema do alinhamento de strings
Alguns problemas NP-completos
• Problema SAT
• Problema da Mochila (com e sem repetição de objetos)
• Problema do Caixeiro Viajante
Problemas de Decisão versus
Problemas de Otimização
• Todo problema de otimização (PO) tem um problema de
decisão associado (PDe) e vice-versa.
Exemplo: Problema do Caixeiro Viajante (CV) é um
problema de otimização.
Versão do problema CV de decisão:
Input: {C1,...,Cn}, matriz n x n de distâncias, B > 0
Output : existe um tour saindo de C1 e voltando a C1,
passando por todas as cidades uma única vez, tal que
seu comprimento total é < B ?
Problemas de otimização NP-hard
• Se o problema de decisão PDe é NP-completo, PO é
NP-hard.
• Problemas da classe NP são problemas de decisão.
• Problemas NP-hard: Seja A um problema de
otimização. Dizemos que A é NP-hard se:
– qualquer problema X(De) da classe NP se reduz a
A(De)
– Repare que A não precisa ser NP (A não é de
decisão !)
Problemas de otimização NP-hard
e programação dinâmica
Programação Dinâmica é uma técnica que
fornece algoritmos mais eficientes do que
o de força bruta para resolver muitos
problemas NP-hard.
Tais algoritmos não são polinomiais !
Problema da Mochila (PM): projetando um
algoritmo PD para PM
Input: W > 0 (peso máximo que a
mochila suporta),
Objetos = {o1,o2,...,on},
Valores = { v1, ..., vn }
Pesos = { p1, ..., pn}
Output: quais objetos escolher de
modo a poder carregar na mochila
e obter o lucro máximo ?
Versão com repetição
É permitido pegar um número qualquer de cópias
de cada objeto.
K(w) = valor máximo que é possivel carregar com
uma mochila de capacidade w.
Subproblemas:
K(w) = max {K(w – wi) + vi : i = 1,...,n, wi ≤ w}
Ideia da fórmula
• Mochila de capacidade W
• Pesos disponiveis abaixo de W: p1, p2, p3
• Para cada peso pi ≤ W podemos pegar o objeto correspondente de
valor vi e colocar na mochila
• O valor na mochila depois de pegar o objeto de peso pi será vi e
sobrará uma capacidade de W – pi
• Os subproblemas a resolver são :
K(W-p1), K(W-p2), K(W-p3)
• Uma vez resolvido estes 3 subproblemas, o problema original K(W)
é resolvido considerando:
max { K(W- p1) + v1, K(W- p2) + v2, K(W – p3) + v3}
Algoritmo
1. K(0) = 0, L = [ ]
2. For w = 1, ..., W
3. K(w) = max {K(w-wi) + vi: wi ≤ W}
4.
i = arg K(w)
5.
L(w) = insert(i, L(w-wi))
6. Retorna L(W)
Complexidade = O(nW)
Algoritmo não é polinomial em W !
Algoritmo é EXPONENCIAL em W, pois a complexidade é medida
em relação ao tamanho da representação da grandeza !
Exemplo de execução
do algoritmo
Como lidar com problemas de
otimização NP-hard ?
• Programação dinâmica produz algoritmos
(exponenciais) mais eficientes que os algoritmos
de força bruta para resolver problemas de
otimização NP-hard.
• Programação linear é outra técnica que produz
algoritmos mais eficientes que os de força bruta
para resolver problemas de otimização NP-hard.
• Algoritmos Aproximados
Algoritmos Aproximados
Para problema de Minimização π
Seja A um algoritmo que resolve π aproximadamente, produzindo resposta A(I)
no input I
Razão de aproximação de A:
αA = max A(x)
x Opt(x)
dentre todos os inputs x do problema
Como se trata de um problema de minimização: αA ≥ 1
αA : mede quantas vezes, no pior caso, a solução aproximada fornecida por A
excede a solução optimal
Algoritmos Aproximados
Para problemas de maximização:
αA = max Opt(x) dentre todos os inputs x do problema
x A(x)
αA : mede quantas vezes, no pior caso, a solução aproximada fornecida por A
fica abaixo da solução da otimal.
Algoritmos Aproximados
• Objetivo de um “bom” algoritmo aproximado:
– Polinomial
– αA é o mais próximo de 1 possivel: αA – 1 é bem pequeno
• Problemas NP-Hard aproximáveis
Um problema NP-hard é aproximável se existe um
algoritmo A de complexidade polinomial que o
aproxima.
Hierarquia de Aproximação dos
Problemas NP-hard
• Problemas Totalmente Aproximáveis
Para todo ε> 0 existe um algoritmo A, polinomial, que aproxima o
problema com razão de aproximação 1 ≤ αA ≤ 1 + ε
Ex. Problema da Mochila, Two-Machine scheduling
• Problemas Parcialmente Aproximáveis: existe algoritmo
polinomial que aproxima o problema com razão
1 ≤ αA ≤ K
Repare que neste caso, nem sempre se encontra um algoritmo
aproximado com razão ‘bem’ próxima de 1.
Ex. Vertex Cover, Caixeiro Viajante “euclidiano”
• Problemas Não-Aproximáveis: Não existe algoritmo polinomial
que o aproxima com razão 1 ≤ αA ≤ K
(a menos que P = NP)
Ex. Problema do Caixeiro Viajante geral