Análise e Síntese de Algoritmos
Programação Dinâmica
CLRS, Cap. 15
Resumo
• Programação dinâmica
– Motivação
– Um exemplo
• Multiplicação de cadeias de matrizes
– Características da programação dinâmica
– Exemplos adicionais
• Problema da mochila
• Maior sub-sequência comum
• Efectuar trocos
2003/2004
Análise e Síntese de Algoritmos
2
Técnicas para Síntese de Algoritmos
• Dividir para conquistar
– MergeSort
• Programação dinâmica
– Floyd-Warshall
• Algoritmos greedy
– Prim, Dijkstra
2003/2004
Análise e Síntese de Algoritmos
3
Programação Dinâmica
• Passos para a realização de um algoritmo baseado
em programação dinâmica:
– Caracterizar estrutura de uma solução óptima
– Definir recursivamente o valor de uma solução óptima
– Calcular valor da solução óptima utilizando abordagem
bottom-up
– Construir solução a partir da informação obtida
2003/2004
Análise e Síntese de Algoritmos
4
Exemplo Simples: Combinações
Formulação recursiva:
1
 n   n  1  n  1
   


 k   k  1  k 
0
2003/2004
se k  0 ou k  n
se 0  k  n
caso contrário
Análise e Síntese de Algoritmos
5
Exemplo (Cont.)
Solução recursiva:
function C(n,k)
if k = 0 or k = n then return 1
else return C(n-1, k-1)+C(n-1,k)
Cada chamada a C(n,k) retorna 1 ou invoca o cálculo
de dois sub-problemas
Solução é calculada somando 1´s !
Tempo de execução é:
n
   
k 
2003/2004
Análise e Síntese de Algoritmos
6
Exemplo (Cont.)
• Número de C(n,k) distintos é nk
• Complexidade da solução recursiva deriva do cálculo
repetido de sub-problemas
– C(5,3) = C(4,2) + C(4,3)
– C(4,2) = C(3,1) + C(3,2)
– C(4,3) = C(3,2) + C(3,3)
• Solução: solução construtiva (bottom-up)
– Preencher tabela (n x k) (triângulo de Pascal)
2003/2004
Análise e Síntese de Algoritmos
7
Construção da Tabela
0
1
2
…
n-1
n
2003/2004
0
1
1
1
1
2
1
2
1
…
k-1
k
c[n-1,k-1]
c[n-1,k]
c[n,k]
Análise e Síntese de Algoritmos
8
Exemplo (Cont.)
• Comentários:
– Problema artificial
• Formulação definida à partida
– Ilustra eliminação de cálculo repetido de sub-problemas
2003/2004
Análise e Síntese de Algoritmos
9
Um Exemplo Adicional
• Multiplicação de cadeias de matrizes
– A1, A2, …, An
• Ai (pi-1 x pi)
– Tempo para multiplicar as n matrizes é dominado pelo
tempo para realizar as multiplicações escalares necessárias
• Para multiplicar duas matrizes (r x s) e (s x t), o número
de multiplicações escalares é: r x s x t
– Número de produtos depende do modo como os produtos
de matrizes são organizados
• Colocação de parêntesis define organização da
multiplicação de matrizes
2003/2004
Análise e Síntese de Algoritmos
10
Um Exemplo (Continuação)
• Caso concreto: A (13x5); B (5x89); C (89x3); D (3x34)
– (((AxB)xC)xD):
• 13x5x89 + 13x89x3 + 13x2x34 = 10582 produtos
– ((AxB)x(CxD)):
• 13x5x89 + 89x3x34 + 13x89x34 = 54201 produtos
– ((Ax(BxC))xD):
• 5x89x3 + 13x5x3 + 13x3x34 = 2856 produtos !
– (Ax((BxC)xD)):
• 5x89x3 + 5x3x34 + 13x5x34 = 4055 produtos
– (Ax(Bx(CxD)))
• 89x3x34 + 5x89x34 + 13x5x34 = 26418 produtos
2003/2004
Análise e Síntese de Algoritmos
11
Formulação do Problema
• Colocar parêntesis numa cadeia de produtos de
matrizes tal que o número de multiplicações
escalares é minimizado
• Número de colocações possíveis de parêntesis
cresce exponencialmente com número de matrizes:
1
n 1

n 1
P(n)   P(k )P(n  k ) n  2

k 1
P(n)  C(n  1)
2003/2004
3
1  2n 
n

C(n) 
    4 n 2 


n  1 n 
Análise e Síntese de Algoritmos
12
Características da Solução Óptima
• Seja A1..n solução com colocação óptima de parêntesis
– Admitir solução óptima com parêntesis em k, A1..kAk+1..n
– Facto:
• Colocação de parêntesis para A1..k é também óptima
– Porquê?
• Caso contrário seria possível encontrar uma melhor
colocação de parêntesis para A1..k e portanto para A1..n
– Conclusão:
• Solução óptima para o problema da colocação de
parêntesis é composta por soluções óptimas para os seus
sub-problemas
2003/2004
Análise e Síntese de Algoritmos
13
Solução Recursiva
• m[i,j]:
– menor número de multiplicações escalares necessário para
calcular matriz Ai..j
– Solução óptima para A1..n é m[1,n]
– i = j:
m[i,j] = 0
– i < j:
• Admitir que solução óptima coloca parêntesis em k:
– m[i,j] = m[i,k] + m[k+1,j] + pi-1pkpj
• Mas qual o valor de k?
– certamente k tem valor entre i e j-1
– considerar todos os valores de k possíveis
• s[i,j]: define colocação óptima de parêntesis entre i e j
2003/2004
Análise e Síntese de Algoritmos
14
Solução Recursiva (Cont.)
Definição de m[i,j]:
i j
0
m[i, j]  
min ik  j  m[i,k ]  m[k  1, j]  pi1pk p j  i  j
Definição de s[i,j]:
s[i, j]  k sse m[i, j]  m[i,k]  m[k  1, j]  pi1pk p j
2003/2004
Análise e Síntese de Algoritmos
15
Cálculo dos Valores de m[i,j]
• Número de subproblemas distintos:
– 1 para cada 1  i  j  n
– número de problemas:  n2
 
• Problema:
– solução recursiva requer tempo exponencial
– resolução repetida dos mesmos subproblemas
• Solução:
– solução construtiva (bottom-up)
– tempo de execução: On3 
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
16
Características da Programação Dinâmica
• Solução óptima do problema composta por soluções
óptimas para sub-problemas
• Solução recursiva resolve repetidamente os mesmos
sub-problemas
– Sobreposição de problemas
– Utilizar solução construtiva para evitar resolver
repetidamente o mesmo problema
• Reconstrução da solução óptima
• Memorização
2003/2004
Análise e Síntese de Algoritmos
17
Outro Exemplo: Problema da Mochila
• Definição do problema:
–
–
–
–
Dados n objectos (1,…,n) e uma mochila
Cada objecto tem um valor vi e um peso wi
Peso transportado pela mochila não pode exceder W
Objectivo:
• maximizar o valor transportado pela mochila e respeitar
a restrição de peso
• Formalização:
– xi = 1 se objecto i incluído na mochila; 0 caso contrário
n
 xivi
max
i 1
n
s.t.
 xiw i  W
i 1
2003/2004
Análise e Síntese de Algoritmos
18
Uma Tentativa
• Algoritmo que a cada passo selecciona objecto com
maior valor vi/wi
• Problema:
– v1 = 8, w1 = 6
– v2 = 5, w2 = 5
– v3 = 5, w3 = 5
– W = 10
– Primeiro objecto seleccionado (objecto 1) impede encontrar
solução óptima (com objectos 2 e 3)
2003/2004
Análise e Síntese de Algoritmos
19
Utilização de Programação Dinâmica
• v[i,j]:
– máximo valor que é possível transportar se o peso limite é j,
( j  W ), e se apenas podem ser seleccionados os objectos
numerados de 1 a i
– Solução óptima encontra-se em v[n,W]
– Definição:
não incluir objecto i
v[i, j]  max v[i  1, j], v[i  1, j  w i ]  v i 
v0, j  0, j  0
vi, j  , j  0
incluir objecto i
vi,0  0
2003/2004
Análise e Síntese de Algoritmos
20
Comentários
• Solução óptima é composta por soluções óptimas
para os sub-problemas:
v[i, j]  max v[i  1, j], v[i  1, j  w i ]  v i 
– Se v[i,j] é solução óptima:
• Se objecto i não é incluído, v[i-1,j] é sub-solução óptima
• Se objecto i é incluído, v[i-1,j-wi] é sub-solução óptima
– Caso contrário, seria possível obter solução com valor
superior ao da solução óptima; uma contradição !
2003/2004
Análise e Síntese de Algoritmos
21
Comentários (Cont.)
• Solução recursiva tem tempo de execução
exponencial em n e W
– Mas: número de sub-problemas distintos é n x W
– Conclusão: resolução repetida dos mesmos sub-problemas !
• Utilizar solução construtiva (bottom-up)
– preencher tabela (n x W)
• Tempo de execução: nW 
– pseudo-polinomial
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
22
Exemplo: Maior Sub-Sequência Comum
• Dada uma sequência X = <x1,…,xn>, uma sequência
Z = <z1,…,zk> é uma sub-sequência de X se existe
uma sequência estritamente crescente <i1,…,ik> tal
que para todo o j = 1,…,k, x i  z j
j
• Dadas as sequências X = <x1,…,xn> e Y = <y1,…,ym>,
Z é uma sub-sequência comum se Z é sub-sequência
de X e de Y
– Obs: Xi = <x1,…,xi>
• Problema: Encontrar sub-sequência comum de maior
comprimento (LCS) entre duas sequências X e Y
2003/2004
Análise e Síntese de Algoritmos
23
Exemplo (Cont.)
• Um caso concreto:
– X = <abefcghd>
– Y = <eagbcfdh>
– Z = <abcd> é sub-sequência comum de X e Y
• Uma solução exaustiva é impraticável:
– Considerar inclusão (ou não) de cada caracter de X e de Y
• Total de sub-sequências em X: 2 n
• Total de sub-sequências em Y: 2m
• Total de casos a analisar:
2n  m
– Impraticável para valores elevados de n e m
2003/2004
Análise e Síntese de Algoritmos
24
Exemplo (Cont.)
• Alguns resultados formais:
– Sejam X = <x1,…,xn> e Y = <y1,…,ym> duas sequências, e
seja Z = <z1,…,zk> uma LCS de X e Y
• Se xn = ym, então zk = xn = ym e Zk-1 é LCS de Xn-1 e Ym-1
• Se xn  ym, então zk  xn implica que Z é LCS de Xn-1 e Y
• Se xn  ym, então zk  ym implica que Z é LCS de X e Ym-1
• Abordagem:
– Se xn = ym, encontrar LCS W de Xn-1 e Ym-1
• Adicionar xn = ym a W permite obter Z
– Se xn  ym, encontrar LCS’s para Xn-1 e Y e para X e Ym-1
• Escolher a maior LCS
2003/2004
Análise e Síntese de Algoritmos
25
Exemplo (Cont.)
• c[i,j]:
– Comprimento da LCS para as sequências Xi e Yj
• Modelo:
0

c[i, j]  c[i  1, j  1]  1
max c[i  1, j], c[i, j  1]

se i  0 ou j  0
se i, j  0 e x i  y j
se i, j  0 e x i  y j
• Tempo de execução: On  m
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
26
Exemplo: Realizar Trocos
• Dado um conjunto de moedas, denominadas 1,…,n,
com valores d1,…,dn, calcular o menor número de
moedas cuja soma de valores é N
– Número ilimitado de moedas de cada denominação
• Solução greedy pode não funcionar:
– v1 = 1; v2 = 5; v3 = 20; v4 = 25
– Troco de 40?!
• Solução baseada em programação dinâmica
2003/2004
Análise e Síntese de Algoritmos
27
Exemplo (Cont.)
• c[i,j]:
– Menor número de moedas necessárias para pagar j
unidades, 0  j  N, utilizando apenas moedas com
denominação entre 1 e i, 1  i  n
– Objectivo é calcular c[n,N]
• Modelo:
não incluir moeda i
c[i,0]  0 1  i  n
c[i, j]  minc[i  1, j], 1  c[i, j  di ]
c[i, j]   i  0 ou j  0
2003/2004
Análise e Síntese de Algoritmos
incluir moeda i
28
Exemplo (Cont.)
• Tempo de execução: On  N
• Exemplo
2003/2004
Análise e Síntese de Algoritmos
29
Memorização (Memoization)
• Permite obter tempo de execução das soluções
bottom-up, mas utilizando abordagem recursiva
– É necessário memorizar resultados de sub-problemas já
resolvidos
• Exemplo: caminhos mais curtos num DAG, com DFS
• Exemplo: cálculo das combinações
– Não calcular todo o triângulo de Pascal
– Calcular apenas as entradas necessárias
– Calcular cada entrada apenas 1 vez
2003/2004
Análise e Síntese de Algoritmos
30
Memorização (Cont.)
• Tabela c[n,k]:
– entradas com k = 0 ou k = n inicializadas com valor 1
– restantes entradas inicializadas com valor -1
• Pseudo-código:
function Cm(n,k)
if c[n-1,k] < 0 then
c[n-1,k] = Cm(n-1,k)
if c[n-1,k-1] < 0 then
c[n-1,k-1] = Cm(n-1,k-1)
return c[n-1, k-1]+c[n-1,k]
2003/2004
Análise e Síntese de Algoritmos
On  k 
31
Revisão
• Programação dinâmica
– Características principais
– Exemplos de aplicação
• A seguir:
– Algoritmos Greedy
2003/2004
Análise e Síntese de Algoritmos
(CLRS, Cap. 16)
32