View
219
Download
0
Category
Preview:
Citation preview
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
2007/2008 Análise e Síntese de Algoritmos 3
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
2007/2008 Análise e Síntese de Algoritmos 4
Técnicas para Síntese de Algoritmos
• Dividir para conquistar– MergeSort
• Programação dinâmica– Floyd-Warshall
• Algoritmos greedy– Prim, Dijkstra
2007/2008 Análise e Síntese de Algoritmos 5
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
2007/2008 Análise e Síntese de Algoritmos 6
Exemplo Simples: Fibonacci
−+−
=
=
=
contrário caso se se
)2()1(
11
00
)(
nfibnfib
n
n
nfib
Formulação recursiva:
2007/2008 Análise e Síntese de Algoritmos 7
Exemplo Simples: Combinações
<<
−+
−
−
==
=
contrário caso0
nk0 sek
1n
1k
1nnk ou 0k se1
k
n
Formulação recursiva:
2007/2008 Análise e Síntese de Algoritmos 8
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
2007/2008 Análise e Síntese de Algoritmos 9
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)
2007/2008 Análise e Síntese de Algoritmos 10
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]
2007/2008 Análise e Síntese de Algoritmos 11
Exemplo (Cont.)
• Comentários:– Problema artificial
• Formulação definida à partida– Ilustra eliminação de cálculo repetido de sub-problemas
2007/2008 Análise e Síntese de Algoritmos 12
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
2007/2008 Análise e Síntese de Algoritmos 13
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
2007/2008 Análise e Síntese de Algoritmos 14
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
2007/2008 Análise e Síntese de Algoritmos 15
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
2007/2008 Análise e Síntese de Algoritmos 16
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
2007/2008 Análise e Síntese de Algoritmos 17
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]:
2007/2008 Análise e Síntese de Algoritmos 18
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
2007/2008 Análise e Síntese de Algoritmos 19
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
2007/2008 Análise e Síntese de Algoritmos 20
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
2007/2008 Análise e Síntese de Algoritmos 21
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)
2007/2008 Análise e Síntese de Algoritmos 22
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 =
2007/2008 Análise e Síntese de Algoritmos 23
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 +−−−=
2007/2008 Análise e Síntese de Algoritmos 24
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Θ
2007/2008 Análise e Síntese de Algoritmos 25
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
=
2007/2008 Análise e Síntese de Algoritmos 26
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 +
2007/2008 Análise e Síntese de Algoritmos 27
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
2007/2008 Análise e Síntese de Algoritmos 28
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 ⋅
2007/2008 Análise e Síntese de Algoritmos 29
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
2007/2008 Análise e Síntese de Algoritmos 30
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
2007/2008 Análise e Síntese de Algoritmos 31
Exemplo (Cont.)
• Tempo de execução:
• Exemplo
( )NnO ⋅
2007/2008 Análise e Síntese de Algoritmos 32
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
2007/2008 Análise e Síntese de Algoritmos 33
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 ⋅
Recommended