Programação Dinâmica:
Redução a um problema de
grafos !
Profa. Sandra de Amo
BCC - UFU
Problemas de Otimização
• Encontrar determinado elemento com custo otimal
(minimo ou máximo).
• Programação Dinâmica
– em geral é ideal para resolver problemas de
otimização
– Tarefas: encontrar
• o custo otimal
• o elemento correspondente ao custo minimal
Problemas que resolvemos até o
momento
Problema 1.
–
Dado um grafo aciclico dirigido G, encontrar caminho com menor
custo.
Algoritmo PD:
1.
Lineariza G;
2.
Para todo vértice x
3.
dist(x) = 
4.
dist(S) = 0; prev(S) = nil
5.
Para cada v  V – {S}, na ordem linear
6.
Para cada aresta e = (u,v) ∈ E
7.
K(u,v) = dist(u) + l(u,v) % dist(u) já foi calculado !!
8. dist(v) = min{K(u,v)}
9.
prev(v) = arg1 (min{K(u,v)}) % o vértice u da aresta (u,v)
correspondente ao valor min { K(u,v) }
Exemplo de execução do algoritmo
dist(D) = min{ dist(B) + 1, dist(C) + 3 } = min{8,5} = 5
prev(D) = C
dist(B) = dist(A) + 6 = 1 + 6 = 7
prev(B) = A
dist(A) = min{ dist(C) + 4, dist(S) + 1} = min{6,1} = 1
prev(A) = S
dist(C) = dist(S) + 2 = 2
prev(C) = S
dist(S) = 0
Caminho mais curto de S para D:
Custo minimo = 5
prev(S) = nil
SCD
Problemas que resolvemos até o momento
Problema 2.
– Dada uma sequência de números {a1,..., an}
encontrar a subsequência mais longa em ordem
crescente.
– Primeira coisa a fazer:
• Transformar o input do problema em um GRAFO
• Transformar o problema em um problema de
encontrar caminho otimal em G
Transformação do problema
original
(1) Transformação do Input em um grafo
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  caminho no grafo !
(2) Transformação do problema em um problema de grafos
Dado um vértice S e um vértice D encontrar o caminho mais longo saindo
de S e chegando em D.
Algoritmo PD
1.
2.
3.
4.
5.
6.
7.
Constrói grafo reverso GR= (V,ER)
Para todo j =1,2,...,n
If Lista de adjacências (em GR ) do vértice j ≠ 
L(j) = 1 + max{ L(i): (j,i)  ER};
prev(j) = arg2 max{ L(i): (j,i)  ER}
Else L(j) = 0; prev(j) = nil
Retorna max{L(j): j = 1,...,n}
Exemplo de Execução do Algoritmo
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)}
L(0) = 0
L(1) = 0
L(2) = 1 + max{L(0), L(1)} = 1
L(3) = 1 + max{L(0), L(1)} = 1
L(4) = 1 + max{L(1)} = 1
L(5) = 1 + max{L(0), L(1), L(4)} = 2
L(6) = 1 + max{L(0), L(2), L(4), L(3), L(1)} = 2
L(7) = 1 + max{L(0), L(1), L(3), L(4), L(5) } = 3
Caminho mais longo:
prev(0) = nil
prev(1) = nil
prev(2) = 1
prev(3) = 1
prev(4) = 1
prev(5) = 4
prev(6) = 2
prev(7) = 5
v5  v7
Resposta do algoritmo
•
•
•
•
•
•
•
•
L(0) = 0
L(1) = 0
L(2) = 1 + max{L(0), L(1)} = 1
L(3) = 1 + max{L(0), L(1)} = 1
L(4) = 1 + max{L(1)} = 1
L(5) = 1 + max{L(0), L(1), L(4)} = 2
L(6) = 1 + max{L(0), L(2), L(4), L(3), L(1)} = 2
L(7) = 1 + max{L(0), L(1), L(3), L(4), L(5) } = 3
prev(0) = nil
prev(1) = nil
prev(2) = 1
prev(3) = 1
prev(4) = 1
prev(5) = 4
prev(6) = 2
prev(7) = 5
Tamanho da sequência mais longa = 3 (com 4 vértices !)
Sequência mais longa
V1  V4  V5  V7
2
3
6
7
Problemas que resolvemos até o momento
Problema 3. Distância de Edição
- Dados dois strings w1 e w2 de tamanhos m e n
respectivamente, encontrar o alinhamento com menor
custo entre w1 e w2.
• Como transformar o input do problema em um
GRAFO
• Como transformar o problema em um problema de
encontrar caminho otimal em G
O Grafo subjacente
•
•
Vértices =
{(i,j) : 0 ≤ i ≤ n, 0 ≤ j ≤ m}
– |V| = (m+1).(n+1) = O(m.n)
Arestas =
– (i-1,j)  (i,j)
– (i-1,j-1)  (i,j)
– (i,j-1)  (i,j)
CUSTOS DAS ARESTAS:
(i-1,j)  (i,j)
(i-1,j-1)  (i,j)
(i,j-1)  (i,j)
custo 1
custo 1 se x[i]  y[i], custo 0 se x[i] = y[i],
custo 1
O problema de alinhamento
• Dado o grafo G dirigido correspondente aos
strings w1 e w2 , encontrar o caminho mais
curto entre o vértice (0,0) e o vértice (m,n)
• Custo do vértice (i,j) = custo do alinhamento
do prefixo (0...i) de w1 com o prefixo (0...j) de
w2
= custo do caminho mais curto entre o vértice
(0,0) e o vértice (i,j)
Exemplo
•
•
W1 = EXPONENTIAL
W2 = POLYNOMIAL
Grafo G correspondente
aos strings w1 e w2
Arestas não tracejadas = custo 1
Arestas tracejadas = custo 0
Responda: Qual o caminho mais curto entre (0,0) e (11,10) ??
Custo do caminho mais curto = custo do vértice (11,10) = 6
Soluções:
Usando Dijkstra: O(|V|2) = O(m2.n2)
– Faça como exercício para casa (a ser incluido na próxima lista de
exercicios)
Usando o algoritmo PD = O(m.n)
For i = 0,1,...,m
E(i,0) = i
If i = 0
prev(0,0) = nil
else prev(i,0) = (i-1,0)
For j = 1,2,...,n
E(0,j) = j
prev(0,j) = (0, j-1)
For i = 1,2,...,m
For j = 1,2,...,n
E(i,j) = min{ E(i-1,j) + 1, E(i,j-1) + 1, E(i-1,j-1) + diff(x[i],y[j]) }
prev(i,j) = arg {min{ E(i-1,j) + 1, E(i,j-1) + 1, E(i-1,j-1) + diff(x[i],y[j])}}
Solução usando o PD: encontrando
o custo minimo
•
Preenche a tabela resolvendo
cada subproblema na seguinte
ordem:
– Resolva os m+1 problemas da
linha 0
– Resolva os m+1 problemas da
coluna 0
– Resolva os problemas da
linha 1, a partir da coluna 1
até a coluna n
– Resolva os problemas da
linha 2, a partir da coluna 2
até a coluna n,
– e assim por diante...
Custo mínimo do alinhamento
Solução usando o PD: encontrando um
alinhamento ideal com custo minimo
•
•
•
•
•
•
Comece no último vértice (11,10)
Determine o prev(11,10)
Determine o prev(prev(11,10)),
E assim por diante até chegar no
vértice (0,0)
Construa o caminho de (0,0) até
(11,10)
Interprete a sequência de vértices
do caminho como um alinhamento
entre EXPONENTIAL e
POLYNOMIAL
Custo mínimo do alinhamento
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o caminho de trás
para a frente
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
-
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
P
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
P
O
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
P
O
L
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
E
P
O
L
Y
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
E
N
P
O
L
Y
N
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
E
N
T
P
O
L
Y
N
O
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
E
N
T
P
O
L
Y
N
O M
-
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
E
N
T
P
O
L
Y
N
O M
-
I
I
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
E
N
T
P
O
L
Y
N
O M
-
I
I
A
A
Construindo o alinhamento
correspondente ao caminho
E
Alinhamento
correspondente
a este caminho :
X
- -
P
O
N
E
N
T
P
O
L
Y
N
O M
-
I
I
A
L
A
L
Outro alinhamento ?
Dê o alinhamento correspondente a este outro caminho de custo 6
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
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 ???