Abordagens para problemas
NP-completos
Katia S. Guimarães
[email protected]
maio/2000
[email protected]
1
Há muito mais sobre NP-completude
O link
 http://np-complete.search.ipupdater.com/
Contém informação e apontadores
para listas de problemas NP-competos
em várias áreas.
maio/2000
[email protected]
2
Classe NP-Completo - Abordagens
Há uma série de técnicas para lidar com
problemas NP-completos. Dependendo da
situação, algumas são mais adequadas do
que outras.
Ex.
- Algoritmos de Aproximação
- Programação Dinâmica (Pseudo-polin.)
- Algoritmos Randômicos
maio/2000
[email protected]
3
Algoritmos de Aproximação
Ex. Problema Bin-Packing
Entrada: Números 0 < x < 1
Saída: Quantos bins de capacidade 1 são
necessários para conter estes números?
Uma entrada poderia ser:
.4 .3 .4 .5 .7 .6 .5 .6
Abordagem 1: FIRST FIT
maio/2000
[email protected]
4
Bin-Packing
Entrada: .4 .3 .4 .5 .7 .6 .5 .6
Abordagem 1: FIRST FIT
Saída: {.4, .3}, { .4, .5}, {.7}, {.6}, {.5}, {.6}
Garantia do FIRST FIT:
 de bins  2  ótimo.
Abordagem 2: DECREASING FIRST FIT
maio/2000
[email protected]
5
Bin-Packing
Entrada: .4 .3 .4 .5 .7 .6 .5 .6
Abordagem 2: DECREASING FIRST FIT
Saída: {.7, .3}, {.6, .4}, { .6, .4}, {.5, .5}
Garantia do DECREASING FIRST FIT:
 de bins  1.25  ótimo.
maio/2000
[email protected]
6
Problema Cobertura de Vértices
• INPUT: Grafo G = (V, E)
• OUTPUT: V’  V, |V’| mínimo, tal que
 α=(v, w)  E, (v  E) ou (w  E).
Heurística
guloso
seria uma
solução?
maio/2000
[email protected]
7
Problema Cobertura de Vértices
O algoritmo guloso opera iterativamente, e a
cada iteração toma um vértice de grau máximo.
Mas a solução encontrada nem sempre é ótima.
Qual seria o pior relacão entre uma solução obtida
pelo algoritmo guloso e uma solução ótima?
maio/2000
[email protected]
8
Problema Cobertura de Vértices
Neste exemplo, guloso daria uma solução ótima.
Qual seria o pior relacão entre uma solução obtida
pelo algoritmo guloso e uma solução ótima?
(Será que você descobre isso sem cursar
Algoritmos 2?)
maio/2000
[email protected]
9
Alg. de aproximação para
Cobertura de Vértices
VC-Approx(G)
C=
E’ = E[G]
while E’  
Seja (u, v) arco de E’
C = C  { u, v }
Remover de E’ qualquer arco incidente em u ou v
return C
PERGUNTA: Qual a aproximação garantida?
maio/2000
[email protected]
10
Problema Soma dos Subconjuntos
Entrada: n números naturais
Saída: Existe uma bipartição dos números
na entrada tal que as somas dos elementos
em cada conjunto seja igual?
Uma entrada poderia ser:
5 3 2 4
Abordagem: Programação Dinâmica
maio/2000
[email protected]
11
Problema Soma dos Subconjuntos
Entrada: 5 3 2
4
Abordagem: Programação Dinâmica
5
3
2
4
0
0
0
0
0
0
x
x
0
x
x
x
0
0
0
x
x
x
x
x
0
0
0
x
0
0
x
x
0
x
x
x
0
0
0
x
0
0
x
x
0 0 0
0 0 0
0 0 0
x x 0
0
0
0
x
Saída: Matriz [n,  xi / 2]
Custo: Tamanho da matriz = n   xi
(Pseudo-Polinomial)
maio/2000
[email protected]
12
Problema Soma dos Subconjuntos
Entrada: 7 3 2
4
Abordagem: Programação Dinâmica
7
3
2
4
1 2
3 4
5 6
7
0
0
0
0
0
x
x
x
0
0
x
x
x
x
x
x
0
0
x
x
0
0
0
x
0
0
0
x
8 9 10 11 12 13 14 15 16
0
0
0
0
0
0
x
x
0
x
x
x
0
0
0
x
0
0
x
x
0
0
0
x
0
0
0
x
0
0
0
0
0
0
0
x
Saída: Matriz [4, 8]
maio/2000
[email protected]
13
Algoritmo de Programação Dinâmica
para Soma dos Subconjuntos
soma  0
para i = 1 .. n faça
soma  soma + A [i]
para j = 0 .. soma faça
M [1, j]  0 /* Zera a 1ª. linha da matriz */
M [1, A[1] ]  1 /* Única soma possível = 1ºelem. do array */
para i = 2 .. n faça
para j = 1 .. soma faça
M [i, j]  M [i-1, j] /* Copia linha anterior */
se (A[i] < j e M [i-1, j-A[i] ]=1) então M[i,j] 1
M [i, A[i] ]  1
devolva ( M [n, soma/2] )
maio/2000
[email protected]
14
A seguir mais uma estratégia
Backtracking ……
maio/2000
[email protected]
15