Análise e Síntese de Algoritmos - Técnico Lisboa ... · 2007/2008 Análise e Síntese de Algoritmos 3 Resumo • Programação dinâmica – Motivação – Um exemplo • Multiplicação

Análise e Síntese de Algoritmos

Programação Dinâmica CLRS, Cap. 15

2007/2008 Análise e Síntese de Algoritmos 2

Contexto

• Revisões [CLRS, Cap. 1-10]• Algoritmos em Grafos [CLRS, Cap. 22-26]

– Algoritmos elementares– Árvores abrangentes– Caminhos mais curtos– Fluxos máximos

• Programação Linear [CLRS, Cap. 29]• Técnicas de Síntese de Algoritmos [CLRS, Cap. 15-16]

– Programação dinâmica– Algoritmos greedy

• Tópicos Adicionais [CLRS, Cap. 32-35]– Emparelhamento de Cadeias de Caracteres– Complexidade Computacional– Algoritmos de Aproximação


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


Técnicas para Síntese de Algoritmos

• Dividir para conquistar– MergeSort

• Programação dinâmica– Floyd-Warshall

• Algoritmos greedy– Prim, Dijkstra


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


Exemplo Simples: Fibonacci

−+−

=

=

=

contrário caso se se

)2()1(

11

00

)(

nfibnfib

n

n

nfib

Formulação recursiva:


Exemplo Simples: Combinações

<<

−+

−

−

==

=

contrário caso0

nk0 sek

1n

1k

1nnk ou 0k se1

k

n

Formulação recursiva:


Exemplo (Cont.)

function C(n,k)if k = 0 or k = n then return 1else return C(n-1, k-1)+C(n-1,k)

Solução recursiva:

Cada chamada a C(n,k) retorna 1 ou invoca o cálculode dois sub-problemasSolução é calculada somando 1´s !Tempo de execução é:

Ω

k

n


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)


Construção da Tabela

0 1 2 … k-1 k0 11 1 12 1 2 1…n-1 c[n-1,k-1] c[n-1,k]n c[n,k]


Exemplo (Cont.)

• Comentários:– Problema artificial

• Formulação definida à partida– Ilustra eliminação de cálculo repetido de sub-problemas


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


Um Exemplo (Continuação)

• Caso concreto: A (13x5); B (5x89); C (89x3); D (3x34)

– (((AxB)xC)xD):• 13x5x89 + 13x89x3 + 13x3x34 = 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


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:

≥−

=

= ∑−

=

2n)kn(P)k(P

1n1)n(P 1n

1k

)1n(C)n(P −=

Ω=

+= 2

3n n4

n

n2

1n1

)n(C


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 seussub-problemas


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


Solução Recursiva (Cont.)

<+++

==

−<≤ jippp]j,1k[m]k,i[m min

ji0]j,i[m

jk1ijki

jk1i ppp]j,1k[m]k,i[m]j,i[mssek]j,i[s −+++==

Definição de m[i,j]:

Definição de s[i,j]:


Cálculo dos Valores de m[i,j]

• Número de subproblemas distintos:– 1 para cada – número de problemas:

• Problema:– solução recursiva requer tempo exponencial– resolução repetida dos mesmos subproblemas

• Solução:– solução construtiva (bottom-up)– tempo de execução:

• Exemplo

( )2nΘ

nji1 ≤≤≤

( )3nO


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 mesmossub-problemas– Sobreposição de problemas

– Utilizar solução construtiva para evitar resolver repetidamente o mesmo problema

• Reconstrução da solução óptima• Memorização


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

1iii

n

1iii

Wwx.t.s

vxmax


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)


Utilização de Programação Dinâmica

• v[i,j]:– máximo valor que é possível transportar se o peso limite é j,

( ), e se apenas podem ser seleccionados os objectos numerados de 1 a i

– Solução óptima encontra-se em v[n,W]– Definição:

Wj ≤

( )ii v]wj,1i[v],j,1i[vmax]j,i[v +−−−=

[ ] 0j,0j,0v ≥= [ ] 0j,j,iv <−∞=

incluir objecto i

não incluir objecto i

[ ] 00,iv =


Comentários

• Solução óptima é composta por soluções óptimas para os sub-problemas:

– 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 !

( )ii v]wj,1i[v],j,1i[vmax]j,i[v +−−−=


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:– pseudo-polinomial

• Exemplo

( )nWΘ


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,

• 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

ji zxj

=


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: • Total de sub-sequências em Y:• Total de casos a analisar:

– Impraticável para valores elevados de n e m

n2m2

mn2 +


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


Exemplo (Cont.)

• c[i,j]:– Comprimento da LCS para as sequências Xi e Yj

• Modelo:

• Tempo de execução:

• Exemplo

( )

≠>−−

=>+−−

==

=

ji

ji

yx e 0j,i se]1j,i[c],j,1i[c max

yx e 0j,i se1]1j,1i[c

0j ou 0i se0

]j,i[c

( )mnO ⋅


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


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:

ni10]0,i[c ≤≤=

0j ou 0i]j,i[c <=+∞=

( )]dj,i[c1 ],j,1i[cmin ]j,i[c i−+−=

não incluir moeda i

incluir moeda i


Exemplo (Cont.)

• Tempo de execução:

• Exemplo

( )NnO ⋅


Memorização (Memoization)

• Permite obter tempo de execução das soluçõesbottom-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


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]

( )knO ⋅


Revisão

• Programação dinâmica– Características principais– Exemplos de aplicação

• A seguir:– Algoritmos Greedy (CLRS, Cap. 16)

Documents

Análise e Síntese de Algoritmos - Técnico Lisboa ... · 2007/2008 Análise e Síntese de Algoritmos 3 Resumo • Programação dinâmica – Motivação – Um exemplo • Multiplicação