Revisão – Prova 3
Programação Dinâmica
Algoritmos Aproximados
Programação Dinâmica
• Técnica algoritmica para resolver problemas de OTIMIZAÇÃO –
que em sua maioria são NP-hard.
• Problema P é reduzido a uma sequência ordenada de
subproblemas P1, P2,...,Pn = P
• Resolve-se completamente cada subproblema na ordem até chegar
a P.
• A solução de um problema Pk consiste em aplicar uma função
simples (de preferência O(1)) às soluções (já encontradas) de
problemas Pi, com i<k.
• Técnica de planejamento introduzida por Richard Bellman nos
anos 50.
Transformação em problema de
grafos
• Em geral, um problema que pode ser
resolvido por Prog. Dinâmica pode ser
transformado em um problema de
encontrar caminho mais curto ou mais
longo em grafos.
Subsequências crescentes mais longas
Seja S uma sequência de números naturais {a1,a2,...,an}
Uma subsequência é um subconjunto de S considerado em
sequência: ai1, ai2, ..., aik
Uma subsequência crescente é uma subsequência de S onde os
números são pegos em ordem estritamente crescente
ai1 < ai2 < ... < aik
Exemplo : S = 5, 2, 8, 6, 3, 6, 9, 7
Subsequência crescente : 2, 3, 6, 9
Problema: Encontrar a subsequência crescente mais longa.
Como reduzir o problema a um
problema de grafos
Associar a S (sequência original) um grafo dirigido acíclico:
Vértices = números da sequência S
Aresta (u,v): se u < v e u aparece antes de v na sequência S
subsequência crescente mais longa = caminho mais longo no grafo
Como usar a técnica de PD para
resolver o problema ?
1. Precisamos encontrar os subproblemas
2. Ordenar os subproblemas em ordem crescente
3. Encontrar uma função que opera sobre resultados de subproblemas já
resolvidos em etapas i < k, a fim de resolver o problema da etapa k
v0
v7
L(7) = comprimento do caminho mais longo finalizando no vértice v7 =
1 + max{L(0), L(1), L(3), L(4), L(5)}
Recursão versus PD
Pior Caso: a sequência está ordenada em ordem crescente.
ARVORE DE
RECURSÃO
Profundidade = n
Nr. de nós = O(2n)
Complexidade = O(2|V|)
Execuções Repetidas !!!
Problema da distância de edição
Problema P:
Input: dois strings x = (x1,...,xn), y = (y1,...,ym)
Output: x’ = (x’1,...,x’k), y’ = (y’1,...,y’k), k ≥ m, tal que custo(x’,y’) é
minimo (= dist_edit(x,y) )
x’1 x’2
y’1 y’2
x’3
y’3
x’k
y’k
Custo(x’,y’) = Σi=1k custo(x’i,y’i)
Custo(xi,yi) = 1 se x’i =‘-’ e y’i = yp (inserção de caracter yp)
ou x’i = xp e y’i = ‘-’ (remoção de carater xp)
ou x’i  y’i e ambos  ‘-’
Custo(xi,yi) = 0 se x’i = y’i
Como projetar o algoritmo de PD para
resolver o problema P ?
Problema P
• E(n,m) = custo mínimo do alinhamento
• Subproblemas E(i,j), com i ≤ n, j ≤ m
• Como ordenar os subproblemas ?
• Como resolver completamente cada subproblema, em
ordem crescente, executando uma função que envolve
os resultados dos subproblemas já resolvidos
anteriormente ?
0
0
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
E(11,10) = custo minimo de um alinhamento
3 possibilidades de alinhamento
0
1)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
3 possibilidades de alinhamento
0
1)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
Custo = diff(x[11], y[10] ) +
+ CUSTO de alinhar prefixos (EXPONENTIA, POLYNOMIA) =
= 0 + E(10, 9)
3 possibilidades de alinhamento
0
2)
0
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
A
L
I
-
3 possibilidades de alinhamento
0
2)
0
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
A
L
I
-
Custo = 1 + CUSTO de alinhar prefixos (EXPONENTIA, POLYNOMIAL) =
= 1 + E(10, 10)
3 possibilidades de alinhamento
0
3)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
-
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
3 possibilidades de alinhamento
0
3)
1
2
3
4
5
6
7
8
9
10
11
E
X
P
O
N
E
N
T
I
A
L
-
0
1
2
3
4
5
6
7
8
9
10
P
O
L
Y
N
O
M
I
A
L
Custo = 1 + CUSTO de alinhar prefixos (EXPONENTIAL, POLYNOMIA) =
= 1 + E(11, 9)
Fórmula
E(m,n) = min {diff(x[m],y[n]) + E(m-1,n-1), 1 + E(m,n-1), 1+ E(m-1,n) }
primeiro alinh.
seg. alinh.
terc. alinh.
Em geral:
E(i,j) = min { diff(x[i],y[j]) + E(i-1,i-1), 1 + E(i,j-1), 1+ E(i-1,j) }
Resumo
O problema do alinhamento de dois strings pode ser resolvido de 2 maneiras:
(1)
Encontrando o grafo correspondente aos dois strings e aplicando Dijkstra
para encontrar o caminho mais curto entre o vértice (0,0) e o vértice
(m,n), onde m e n são os tamanhos dos 2 strings.
(2)
Aplicando o algoritmo PD para determinar o caminho de custo minimo
Uma vez encontrado o caminho mais curto usando um dos dois algoritmos,
interprete cada vértice do caminho como uma operação de inserção,
deleção ou substituição e construa o alinhamento.
VER SLIDES DETALHADOS DA AULA 25
Algumas regras para projetar um algoritmo de PD
O problema é determinar os subproblemas e ordená-los !
Regras:
(1)
O input é x1, x2, ..., xn um subproblema é x1, x2, ..., xi
Número de subproblemas = O(n)
(2)
O input é x1, x2, ..., xn um subproblema é xi, x2, ..., xj
Número de subproblemas = O(n2)
(3)
Se o input é x1,x2,...,xn e y1,y2,...,ym um subproblema é
x1,x2,...,xi e y1,y2,...,yj
Número de subproblemas = O(m.n)
(4) O input é uma árvore de n nós, um subproblema é uma subárvore
Exercicio: Quantos subproblemas ???
Programação Dinâmica para lidar com
problemas de otimização NP-Hard:
1) Problema da Mochila: com e sem
repetição
2) Problema do Caixeiro Viajante (geral,
não necessariamente euclidiano.
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 !
Ideia
Problema a resolver K(10,4)
Mochila: 10 kg
Item
Peso
Valor
1
6
30
2
3
14
3
4
16
4
2
9
Começa no último item : 4
Seu peso é ≤ 10 ?
Se Sim:
Tenho duas opções:
1. Coloco o item na mochila :
subproblema a resolver K(10-2, 3)
2. Não coloco o item na mochila
subproblema a resolver K(10,3)
Resultado = max{K(10-2,3) + 9, K(10,3) }
Se Não:
subproblema a resolver K(10,3)
Resultado = resultado de K(10,3)
Pseudo-código do Algoritmo – VER
DETALHES NA AULA 27
1. For j = 0,...,n
2.
K(0,j) = 0, L(0,j) = [ ]
3. For w = 0,...,W
4.
K(w,0) = 0, L(w,0) = [ ]
5. For j = 1 ... n
6.
For w = 1, ..., W
7.
If wj > w: K(w,j) = K(w,j-1)
8.
else:
9.
K(w,j) = max {K(w-wj,j-1) + vj, K(w,j-1)}
10.
(x,y) = arg K(w,j)
11.
L(w,j) = insert(j, L(x,y))
12. Retorna K(W,n) e L(W,n)
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 !
Um outro algoritmo PD para o Problema da
Mochila sem repetição (complexidade O(nV))
Este problema foi proposto na Lista Aula 26-27 (Exercicio 3)
Sejam: V = v1+ v2+ ... + vn = soma dos valores dos itens
n = número de itens
W = capacidade máxima da mochila.
Idéia: Considerar a função W(i,v) onde:
W(i,v) = capacidade mínima da mochila para obter um lucro v usando itens 1,...,v
se possivel
Objetivo: encontrar max{v: W(n,v) ≤ W}
Assim, temos de resolver (no pior caso) V problemas, um para cada v em [1,...,V] e
encontrar o max destes valores
Cada problema W(i,v) é resolvido da seguinte maneira:
W(i,v) = min{W(i-1,v), W(i-1,v-vi) + pi}
W(0,0) = 0
W(0,v) = inf (se v > 0)
Pseudo – código do Algoritmo
1.
2.
3.
4.
5.
6.
7.
8.
9.
W(0,0) = 0 ; L(0,0) = [ ]
For v = 1,...,V
W(0,v) = inf ; L(0,v) = [ ]
For i = 1,...,n
For v = 0, ..., V
W(i,v) = min{W(i-1,v), W(i-1,v-vi)+pi}
If W(i,v) = W(i-1,v): L(i,v) = L(i-1,v);
If W(i,v) = W(i-1,v-vi) + pi : L(i,v) = L(i-1,v-vi)  {i}
Retorna max{v: W(n,v) ≤ W} e L(n,v)
Complexidade = O(nV)
Algoritmo não é polinomial em V !
Algoritmo é EXPONENCIAL em V, pois a complexidade é medida
em relação ao tamanho da representação da grandeza !
Problema do Caixeiro Viajante
Hierarquia de Aproximação para
Problemas NP-completos
1. Não aproximáveis
Caixeiro Viajante geral
Clique, Conj. Independente
2. Parcialmente aproximáveis
Vertex Cover, Clustering, Caixeiro
Viajante “euclidiano”
3. Totalmente aproximáveis
Mochila, Two-machine scheduling,...
Problema do Vertex Cover
Input: Grafo G = (V,E) não-dirigido
Output: Menor V’  V cobrindo todas as arestas de E (qualquer aresta {u,v} tem
uma de suas extremidades em V’)
Vertex Cover é NP-hard
Vertex Cover é parcialmente aproximável.
Ideia geral do algoritmo
aproximado
• Constrói um matching maximal
– Matching = conjunto de arestas que não possuem vértices em
comum
– Matching maximal = se acrescentar mais uma aresta deixa de
ser matching
– Construção do matching maximal: feito em tempo polinomial
• Considera S = vértices do matching maximal
Exemplo
Grafo G
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
Construindo o matching maximal....
Exemplo
Grafo G
MATCHING MAXIMAL !!
Exemplo
Grafo G
VERTEX COVER PRODUZIDO
PELO ALGORITMO APROXIMADO !!
Exemplo
12 vértices !
Grafo G
VERTEX COVER PRODUZIDO
PELO ALGORITMO APROXIMADO !!
VERTEX COVER OTIMAL : 8 Vértices
PROVA: ALGORITMO APROXIMA
PARCIALMENTE O VC
• VER DETALHES NA AULA 29
Algoritmo Aproximado para o Problema do
Caixeiro Viajante EUCLIDIANO
Ideia geral do algoritmo aproximado – DETALHES NA AULA 29
• Considera o grafo associado
G = (V,E), onde V = conj. de cidades ; E ´= V x V; custo({i,j}) = dij
• Constrói uma MST de G
• Considera caminho C obtido percorrendo a MST saindo de C1 e
voltando para C1, mesmo que tenha de passar por um trecho mais
de uma vez.
• “Conserta” este caminho C de modo a eliminar revisitas a cidades já
visitadas, inserindo desvios mais curtos a cada vez que o caminho
C vai revisitar uma cidade.
Exemplo
Wichita
Tulsa
Amarillo
Albuquerque
Little Rock
Dallas
Houston
El Paso
San Antonio
Input do Caixeiro Viajante: conjunto de cidades a visitar.
Qual o tour de custo minimo saindo de e voltando para San Antonio ?
Exemplo
Wichita
Tulsa
Amarillo
Albuquerque
Little Rock
Dallas
Houston
El Paso
San Antonio
Grafo completo correspondente ao conjunto de cidades, todas
interligadas.
Exemplo
UMA MST PARA O GRAFO G
Exemplo
Já foi visitado !
Todos foram
visitados !
Pega o atalho
direto para
San Antonio
Percorre a MST, saindo de San Antonio e voltando para San Antonio,
passando por todas as cidades
Exemplo
Já foi visitado !
Tour produzido pelo algoritmo aproximado
Problema da Mochila
(sem repetição)
Input: W > 0 (capacidade máxima da mochila)
itens 1,2,...,n, pesos p1, p2,..., pn, valores v1, v2,..., vn
Output: Conjunto de itens (sem repetição) com soma total máxima que se
pode carregar na mochila
Mochila é NP-hard – Problema de MAXIMIZAÇÃO
Mochila é Totalmente Aproximável.
Vamos mostrar que para qualquer ε > 0 existe um algoritmo polinomial A tal que
OPT ≤ A (1 + ε / (1 – ε) )
Muito pequeno
Razão de aproximação
ɑ = OPT / A ≤ (1 + ε / (1 – ε) )
Ideia do Algoritmo
•
Ideia central:
– considerar o algorimo de Programação Dinâmica O(nV) que resolve o problema
da mochila sem repetição (ver exercicio 3 – lista Aula 26-27), onde V = total dos
valores dos itens disponíveis.
– Aplicar este algoritmo sobre os valores escalados de modo que a
complexidade em V não seja muito grande !
– Ex. se os valores são v1 = 202.479, v2 = 40.000, v3 = 87.500
considera-se os valores v’1 = 202, v’2 = 40, v’3 = 87 e aplica-se o algoritmo
O(nV) para estes valores.
– Os artigos retornados por este algoritmo caberão na mochila, já que os pesos
não foram alterados.
– Tais artigos podem não corresponder à solução optimal, mas o valor total
(original) dos itens propostos pelo algoritmo aproximado ficará bem
próximo do valor optimal.
Algoritmo
Seja ε > 0 dado.
Consideramos o Algoritmo A (abaixo) que vai aproximar a solução otimal K*
da Mochila de um fator ɑ ≤ 1 + ε(1- ε)
Escala
vi ≤ vi. n/ ε.vmax
Logo: vi ≥ vi ε.vmax/n
Complexidade de A
• Complexidade de A = O(nV’), onde V’ = soma total dos valores dos
itens escalonados.
• Para todo i : v’i ≤ vi . n/ε.vmax ≤ vmax. n/ε.vmax = n/ε
• Logo V’ = Σ v’i ≤ Σ n/ε = n2/ε
• Logo O(nV’) ≤ O(n3/ε) : polinomial em n