Upload
delacyr-ferreira
View
1.559
Download
1
Embed Size (px)
Citation preview
Analise de Algoritmos
Programação Dinâmica
–p. 1/56
Programação Dinâmica
Aplicável a problemas de otimização
– p. 2/56
Programação Dinâmica
Aplicável a problemas de otimização
Combina soluções de subproblemas
–p. 2/56
Programação Dinâmica
Aplicável a problemas de otimização
Combina soluções de subproblemas
Subproblemas não são independentes
– p. 2/56
Programação Dinâmica
Aplicável a problemas de otimização
Combina soluções de subproblemas
Subproblemas não são independentes
A relação problema – subproblema égeralmente expressa em termos de umafórmula recursiva, que quando implementadana forma “bottom-up” produz, em muitos casos,solução eficiente
– p. 2/56
Programação Dinâmica
A diferença para o método guloso é que muitassequências de decisões são geradas, enquantoque no método guloso apenas uma sequênciade decisão é gerada
– p. 3/56
Programacao Dinamica
Multiplicação de matrizes
–p. 4/56
Multiplicação de matrizes
Problema: Multiplicar n matrizes
M = M1 !M2 ! · · ·!Mn
realizando o número mínimo de operações
– p. 5/56
Multiplicação de matrizes
Problema: Multiplicar n matrizes
M = M1 !M2 ! · · ·!Mn
realizando o número mínimo de operações
Em outras palavras, determinar qual a melhorforma de realizar as multiplicações, ou seja, aquelaque requer o número mínimo de operações
– p. 5/56
Multiplicação de matrizes
As matrizes são multiplicadas aos pares
– p. 6/56
Multiplicação de matrizes
As matrizes são multiplicadas aos pares
Vamos supor que cada matrizMi temdimensões bi"1 ! bi. Logo, para calcularMi !Mi+1 são necessárias bi"1 # bi # bi+1
operações
– p. 6/56
Multiplicação de matrizes
Exemplo: M = M1 !M2 !M3 !M4 comb = {200, 2, 30, 20, 5}.
– p. 7/56
Multiplicação de matrizes
Exemplo: M = M1 !M2 !M3 !M4 comb = {200, 2, 30, 20, 5}.
Quantas multiplicações são realizadas nassequências:
M = (((M1 !M2)!M3)!M4)
M = (M1 ! ((M2 !M3)!M4))
– p. 7/56
Multiplicação de matrizes
Exemplo: M = M1 !M2 !M3 !M4 comb = {200, 2, 30, 20, 5}.
Quantas multiplicações são realizadas nassequências:
M = (((M1 !M2)!M3)!M4) $ 152.000 operaçõesM = (M1 ! ((M2 !M3)!M4)) $ 3.400 operações
– p. 8/56
Multiplicação de matrizes
Exemplo: M = M1 !M2 !M3 !M4 comb = {200, 2, 30, 20, 5}.
Quantas multiplicações são realizadas nassequências:
M = (((M1 !M2)!M3)!M4) $ 152.000 operaçõesM = (M1 ! ((M2 !M3)!M4)) $ 3.400 operações
Conclusão: a ordem das multiplicações faz muitadiferença.
– p. 8/56
Multiplicação de matrizes
Como determinar uma sequência ótima demultiplicação?
–p. 9/56
Multiplicação de matrizes
Como determinar uma sequência ótima demultiplicação?
O algoritmo da “força bruta” é impraticável: existem!(2n) possibilidades (números de Catalão).
– p. 9/56
Multiplicação de matrizes
Como determinar uma sequência ótima demultiplicação?
O algoritmo da “força bruta” é impraticável: existem!(2n) possibilidades (números de Catalão).
Pelo método da programação dinâmica, podemosdeterminar eficientemente uma sequência ótima demultiplicação.
– p. 9/56
Multiplicação de matrizes
Para resolver este problema, tudo que precisamosé saber qual o melhor índice k tal que
M = (M1!M2! · · ·!Mk).(Mk+1!Mk+2! · · ·!Mn)
onde k varia de 1 a n" 1.
– p. 10/56
Multiplicação de matrizes
Mais precisamente, sejaMij o número mínimo deoperações para realizar o produto
Mi !Mi+1 ! · · ·!Mj
– p. 11/56
Multiplicação de matrizes
Mais precisamente, sejaMij o número mínimo deoperações para realizar o produto
Mi !Mi+1 ! · · ·!Mj
Podemos calcularMij?
–p. 11/56
Multiplicação de matrizes
Mais precisamente, sejaMij o número mínimo deoperações para realizar o produto
Mi !Mi+1 ! · · ·!Mj
Podemos calcularMij? Sim.
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
– p. 11/56
Multiplicação de matrizes
Esta expressão constitui uma recorrência típica dométodo de programação dinâmica. Ela sugere umalgoritmo recursivo, mas uma implementação“bottom-up” é mais eficiente.
– p. 12/56
Multiplicação de matrizes
Um algoritmo baseado nesta fórmula tem osseguintes passos iterativos:
1. osMi,i são calculados, para 1 % i % n.Claramente,Mi,i = 0, para todo i;
2. osMi,i+1 são calculados, para 1 % i % n" 1;
3. osMi,i+2 são calculados, para 1 % i % n" 2;
4. ... e assim por diante.
– p. 13/56
Multiplicação de matrizes
Por exemplo, vamos aplicar o algoritmo acima paraas seguintes matrizes:
M = M1 ! M2 ! M3 ! M4
(200! 2) (2! 30) (30! 20) (20! 5)
(b0 ! b1) (b1 ! b2) (b2 ! b3) (b3 ! b4)
– p. 14/56
Multiplicação de matrizes
Por exemplo, vamos aplicar o algoritmo acima paraas seguintes matrizes:
M = M1 ! M2 ! M3 ! M4
(200! 2) (2! 30) (30! 20) (20! 5)
(b0 ! b1) (b1 ! b2) (b2 ! b3) (b3 ! b4)
M1,1 = M2,2 = M3,3 = M4,4 = 0
– p. 14/56
Multiplicação de matrizes
Por exemplo, vamos aplicar o algoritmo acima paraas seguintes matrizes:
M = M1 ! M2 ! M3 ! M4
(200! 2) (2! 30) (30! 20) (20! 5)
(b0 ! b1) (b1 ! b2) (b2 ! b3) (b3 ! b4)
M1,1 = M2,2 = M3,3 = M4,4 = 0
M1,2 = 12000, M2,3 = 1200, M3,4 = 3000
– p. 14/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
– p. 15/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
M1,3 = min{M1,k +Mk+1,3 + b0bkb3}, k = 1, 2
– p. 15/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
M1,3 = min{M1,k +Mk+1,3 + b0bkb3}, k = 1, 2
M1,3 = min{M1,1 +M2,3 + b0b1b3,M1,2 +M3,3 + b0b2b3}= min{0 + 1200 + 8000, 12000 + 0 + 120000}= 9200 (M1 ! (M2 !M3))
– p. 15/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
– p. 16/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
M2,4 = min{M2,k +Mk+1,4 + b1bkb4}, k = 2, 3
– p. 16/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
M2,4 = min{M2,k +Mk+1,4 + b1bkb4}, k = 2, 3
M2,4 = min{M2,2 +M3,4 + b1b2b4,M2,3 +M4,4 + b1b3b4}= min{0 + 3000 + 300, 1200 + 0 + 200}= 1400 ((M2 !M3)!M4))
– p. 16/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
– p. 17/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
M1,4 = min{M1,k +Mk+1,4 + b0bkb4}, k = 1, 3
– p. 17/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
M1,4 = min{M1,k +Mk+1,4 + b0bkb4}, k = 1, 3
M1,4 = min{M1,1 +M2,4 + b0b1b4,M1,2 +M3,4 + b0b2b4,
M1,3 +M4,4 + b0b3b4}= min{0 + 1400 + 2000, 12000 + 3000 + 30000,
9200 + 0 + 20000}= 3400 (M1 ! ((M2 !M3)!M4))
– p. 17/56
Multiplicação de matrizes
Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1
M1,4 = min{M1,k +Mk+1,4 + b0bkb4}, k = 1, 3
M1,4 = min{M1,1 +M2,4 + b0b1b4,M1,2 +M3,4 + b0b2b4,
M1,3 +M4,4 + b0b3b4}= min{0 + 1400 + 2000, 12000 + 3000 + 30000,
9200 + 0 + 20000}= 3400 (M1 ! ((M2 !M3)!M4))
Solução ótima: (M1 ! ((M2 !M3)!M4))
– p. 17/56
Exercícios1. Aplique o algoritmo para multiplicar 5 matrizes, onde
b = {30, 35, 15, 5, 10, 20}2. Descreva mais precisamente o algoritmo estudado3. Quantas operações são realizadas por este algoritmo?4. Considere a seguinte proposta gulosa para a solução
do problema de multiplicação de matrizes: a cadapasso, selecione o produto que requer um númeromínimo de operações
5. Apresente uma solução para a variante do problema demultiplicação de matrizes em que o objetivo émaximizar o número de operações
– p. 18/56
Programacao Dinamica
Maior subsequência comum
–p. 19/56
Maior subsequência comum
Problema: Dadas as sequênciasX = &x1, x2, . . . , xm' e Y = &y1, y2, . . . , yn', encontraruma subsequência comum de maior tamanho(LCS(X,Y )).
– p. 20/56
Maior subsequência comum
Problema: Dadas as sequênciasX = &x1, x2, . . . , xm' e Y = &y1, y2, . . . , yn', encontraruma subsequência comum de maior tamanho(LCS(X,Y )).
springtime horseback
snowflakepioneer
– p. 20/56
Maior subsequência comum
Uma subsequência não necessita ter elementosconsecutivos; Ela deve ter apenas elementos namesma ordem na sequência.
– p. 21/56
LCS – Algoritmo força bruta
Para cada subsequência de X, verifique se elaé subsequência de Y .
– p. 22/56
LCS – Algoritmo força bruta
Para cada subsequência de X, verifique se elaé subsequência de Y .
Qual o tempo?
–p. 22/56
LCS – Algoritmo força bruta
Para cada subsequência de X, verifique se elaé subsequência de Y .
Qual o tempo?
2m subsequências de X para verificar (poiscada subsequência de X corresponde a umsubconjunto de {1, 2, . . . ,m}) + tempo linearpara verificar cada uma.
– p. 22/56
LCS – Algoritmo força bruta
Para cada subsequência de X, verifique se elaé subsequência de Y .
Qual o tempo?
2m subsequências de X para verificar (poiscada subsequência de X corresponde a umsubconjunto de {1, 2, . . . ,m}) + tempo linearpara verificar cada uma.
Portanto, esta não é uma boa estratégia.
– p. 22/56
LCS – Algoritmo força bruta
Podemos fazer melhor?
– p. 23/56
LCS – Algoritmo força bruta
Podemos fazer melhor?Sim, utilizando programação dinâmica.
– p. 23/56
LCS – Algoritmo força bruta
Podemos fazer melhor?Sim, utilizando programação dinâmica.
Notação:
Xi = &x1, x2, . . . , xi', o i-ésimo prefixo de X
Yi = &y1, y2, . . . , yi', o i-ésimo prefixo de Y
– p. 23/56
Maior subsequência comum
Uma LCS(X,Y ) pode ser obtida recursivamenteda seguinte forma:
– p. 24/56
Maior subsequência comum
Uma LCS(X,Y ) pode ser obtida recursivamenteda seguinte forma:
Se xm = yn então uma LCS(X,Y ) é formadapor uma LCS(Xm"1, Yn"1) concatenada com&xm'
– p. 24/56
Maior subsequência comum
Uma LCS(X,Y ) pode ser obtida recursivamenteda seguinte forma:
Se xm = yn então uma LCS(X,Y ) é formadapor uma LCS(Xm"1, Yn"1) concatenada com&xm'
Se xm (= yn então uma LCS(X,Y ) é formadapor uma LCS(Xm, Yn"1) ou LCS(Xm"1, Yn)
– p. 24/56
Maior subsequência comum
Defina c(i, j) como o tamanho da LCS(Xi, Yj).
– p. 25/56
Maior subsequência comum
Defina c(i, j) como o tamanho da LCS(Xi, Yj).Então
c(i, j) =
!"""#
"""$
0 se i = 0 ou j = 0
c(i" 1, j " 1) + 1 se xi = yj
max{c(i" 1, j), c(i, j " 1)} se xi (= yj
– p. 25/56
Maior subsequência comum
Defina c(i, j) como o tamanho da LCS(Xi, Yj).Então
c(i, j) =
!"""#
"""$
0 se i = 0 ou j = 0
c(i" 1, j " 1) + 1 se xi = yj
max{c(i" 1, j), c(i, j " 1)} se xi (= yj
Podemos implementar eficientemente esta fórmulacalculando os c(i, j) para valores crescentes de i ej até calcular c(m,n).
– p. 25/56
Maior subsequência comum
Vamos calcular LCS(X,Y ), ondeX = ABCB e Y = BDCAB.
– p. 26/56
Maior subsequência comum
Vamos calcular LCS(X,Y ), ondeX = ABCB e Y = BDCAB.
Xi
Yj
A
A
B
B
B B
C
CD
0
0
0
000000
0
– p. 26/56
Maior subsequência comum
Vamos calcular LCS(X,Y ), ondeX = ABCB e Y = BDCAB.
Xi
Yj
A
A
B
B
B B
C
CD
00
0
0
0
0
000000
0
– p. 27/56
Maior subsequência comum
Vamos calcular LCS(X,Y ), ondeX = ABCB e Y = BDCAB.
Xi
Yj
A
A
B
B
B B
C
CD
000
0
0
0
0
000000
1 1
– p. 28/56
Maior subsequência comum
Vamos calcular LCS(X,Y ), ondeX = ABCB e Y = BDCAB.
Xi
Yj
A
A
B
B
B B
C
CD
000
0
0
0
0
000000
11
11
1111
11
22
222
2
3
– p. 29/56
LCS - exemplo para completar
Ex.: X = (A,B,C,B,D,A,B) e Y = (B,D,C,A,B,A).
Yj B D C A B AXi 0 0 0 0 0 0 0A 0B 0C 0B 0D 0A 0B 0
– p. 30/56
Maior subsequência comum
Qual o tempo gasto pelo algoritmo?
–p. 31/56
Maior subsequência comum
Qual o tempo gasto pelo algoritmo? O(m.n)
– p. 31/56
Maior subsequência comum
Qual o tempo gasto pelo algoritmo? O(m.n)
Como encontrar uma LCS(X,Y ) após completadaa tabela? Qual o tempo?
–p. 31/56
Exercícios1. Determine uma LCS para X = &1, 0, 0, 1, 0, 1, 0, 1' e
Y = &0, 1, 0, 1, 1, 0, 1, 1, 0'2. Descreva mais precisamente o algoritmo estudado3. Mostre como computar o comprimento de uma LCS
usando apenas 2.min(m,n) entradas (2 linhas oucolunas da tabela)
4. Forneça um algoritmo O(n2) para encontrar uma maiorsubsequência não descrescente de uma dadasequência de n números
– p. 32/56
Exercícios5. Forneça um algoritmo O(n log n) para encontrar uma
maior subsequência não descrescente de uma dadasequência de n números
– p. 33/56
Programacao Dinamica
O problema do caixeiro viajante
–p. 34/56
Caixeiro viajante (PCV)
O PCV consiste em encontrar um circuito de customínimo que contém todos os vertices (circuitohamiltoniano) em um grafo G com custos nãonegativos cij associados à cada aresta (i, j).
– p. 35/56
Caixeiro viajante (PCV)
Vamos supor, sem perda de generalidade, que osvértices estão numerados de 1 a n, e que o circuitocomeça e termina no vértice 1.
– p. 36/56
Caixeiro viajante (PCV)
Vamos supor, sem perda de generalidade, que osvértices estão numerados de 1 a n, e que o circuitocomeça e termina no vértice 1.
OBS: qualquer circuito hamiltoniano é constituídopor uma aresta (1, k), 2 % k % n, e um caminho dek até 1 que contém todos os vértices deV (G)" {1, k}. Esta observação nos motiva adefinir a seguinte função.
– p. 36/56
Caixeiro viajante
Seja f(i, C) o custo de um caminho mínimo dovértice i até 1 e que visita todos os vértices doconjunto C.
– p. 37/56
Caixeiro viajante
Seja f(i, C) o custo de um caminho mínimo dovértice i até 1 e que visita todos os vértices doconjunto C.
Podemos calcular f(i, C)?
–p. 37/56
Caixeiro viajante
Seja f(i, C) o custo de um caminho mínimo dovértice i até 1 e que visita todos os vértices doconjunto C.
Podemos calcular f(i, C)? Sim. Os valores def(i, C) podem ser calculados recursivamente daseguinte forma:
f(i, C) = minj)C{cij + f(j, C " {j})}
– p. 37/56
Caixeiro viajante
Os valores de f(i, C) podem ser calculadosrecursivamente da seguinte forma:
f(i, C) = minj)C{cij + f(j, C " {j})}
– p. 38/56
Caixeiro viajante
Os valores de f(i, C) podem ser calculadosrecursivamente da seguinte forma:
f(i, C) = minj)C{cij + f(j, C " {j})}
A solução do PCV está no cálculo de
f(1, V (G)"{1}) = min2%k%n{c1k+f(k, V (G)"{1, k})}
– p. 38/56
Caixeiro viajante
Os valores de f necessários para resolver o PCVpodem ser obtidos em ordem crescente de |C|, daseguinte forma:
– p. 39/56
Caixeiro viajante
Os valores de f necessários para resolver o PCVpodem ser obtidos em ordem crescente de |C|, daseguinte forma:
|C| = 0: f(i, *) = ci1, + 2 % i % n.
– p. 39/56
Caixeiro viajante
Os valores de f necessários para resolver o PCVpodem ser obtidos em ordem crescente de |C|, daseguinte forma:
|C| = 0: f(i, *) = ci1, + 2 % i % n.
|C| = 1: f(i, {j}) = cij + f(j, *) = cij + cj1,+ 2 % i, j % n, i (= j.
– p. 39/56
Caixeiro viajante
Os valores de f necessários para resolver o PCVpodem ser obtidos em ordem crescente de |C|, daseguinte forma:
|C| = 0: f(i, *) = ci1, + 2 % i % n.
|C| = 1: f(i, {j}) = cij + f(j, *) = cij + cj1,+ 2 % i, j % n, i (= j.
|C| = 2, 3, . . . , n" 2, usa-se a fórmula geral,utilizando os valores de f calculadosanteriormente.
– p. 39/56
Caixeiro viajante - exemplo
1
110
2 77
121
59 3
15
20
3
2 4
– p. 40/56
Caixeiro viajante - exemplo
1
110
2 77
121
59 3
15
20
3
2 4
f(2, {3}) = c23 + c31 = 9 + 1 = 10
– p. 40/56
Caixeiro viajante - exemplo
1
110
2 77
121
59 3
15
20
3
2 4
f(2, {3}) = c23 + c31 = 9 + 1 = 10f(2, {4}) = c24 + c41 = 1 + 7 = 8
– p. 40/56
Caixeiro viajante - exemplo
1
110
2 77
121
59 3
15
20
3
2 4
f(2, {3}) = c23 + c31 = 9 + 1 = 10f(2, {4}) = c24 + c41 = 1 + 7 = 8f(3, {2}) = c32 + c21 = 5 + 20 = 25
– p. 40/56
Caixeiro viajante - exemplo
1
110
2 77
121
59 3
15
20
3
2 4
f(2, {3}) = c23 + c31 = 9 + 1 = 10f(2, {4}) = c24 + c41 = 1 + 7 = 8f(3, {2}) = c32 + c21 = 5 + 20 = 25f(3, {4}) = c34 + c41 = 15 + 7 = 22
– p. 40/56
Caixeiro viajante - exemplo
1
110
2 77
121
59 3
15
20
3
2 4
f(2, {3}) = c23 + c31 = 9 + 1 = 10f(2, {4}) = c24 + c41 = 1 + 7 = 8f(3, {2}) = c32 + c21 = 5 + 20 = 25f(3, {4}) = c34 + c41 = 15 + 7 = 22f(4, {2}) = c42 + c21 = 12 + 20 = 32
– p. 40/56
Caixeiro viajante - exemplo
1
110
2 77
121
59 3
15
20
3
2 4
f(2, {3}) = c23 + c31 = 9 + 1 = 10f(2, {4}) = c24 + c41 = 1 + 7 = 8f(3, {2}) = c32 + c21 = 5 + 20 = 25f(3, {4}) = c34 + c41 = 15 + 7 = 22f(4, {2}) = c42 + c21 = 12 + 20 = 32f(4, {3}) = c43 + c31 = 3 + 1 = 4
– p. 40/56
Caixeiro viajante - exemplo
f(2, {3, 4}) = min{c23 + f(3, {4}), c24 + f(4, {3})}
– p. 41/56
Caixeiro viajante - exemplo
f(2, {3, 4}) = min{c23 + f(3, {4}), c24 + f(4, {3})}= min{9 + 22, 1 + 4} = 5 (j = 4)
– p. 41/56
Caixeiro viajante - exemplo
f(2, {3, 4}) = min{c23 + f(3, {4}), c24 + f(4, {3})}= min{9 + 22, 1 + 4} = 5 (j = 4)
f(3, {2, 4}) = min{c32 + f(2, {4}), c34 + f(4, {2})}
– p. 41/56
Caixeiro viajante - exemplo
f(2, {3, 4}) = min{c23 + f(3, {4}), c24 + f(4, {3})}= min{9 + 22, 1 + 4} = 5 (j = 4)
f(3, {2, 4}) = min{c32 + f(2, {4}), c34 + f(4, {2})}= min{5 + 8, 15 + 32} = 13 (j = 2)
– p. 41/56
Caixeiro viajante - exemplo
f(2, {3, 4}) = min{c23 + f(3, {4}), c24 + f(4, {3})}= min{9 + 22, 1 + 4} = 5 (j = 4)
f(3, {2, 4}) = min{c32 + f(2, {4}), c34 + f(4, {2})}= min{5 + 8, 15 + 32} = 13 (j = 2)
f(4, {2, 3}) = min{c42 + f(2, {3}), c43 + f(3, {2})}
– p. 41/56
Caixeiro viajante - exemplo
f(2, {3, 4}) = min{c23 + f(3, {4}), c24 + f(4, {3})}= min{9 + 22, 1 + 4} = 5 (j = 4)
f(3, {2, 4}) = min{c32 + f(2, {4}), c34 + f(4, {2})}= min{5 + 8, 15 + 32} = 13 (j = 2)
f(4, {2, 3}) = min{c42 + f(2, {3}), c43 + f(3, {2})}= min{12 + 10, 3 + 25} = 22 (j = 2)
– p. 41/56
Caixeiro viajante - exemplo
f(1, {2, 3, 4}) = min{c12 + f(2, {3, 4}),c13 + f(3, {2, 4}),c14 + f(4, {2, 3})}
– p. 42/56
Caixeiro viajante - exemplo
f(1, {2, 3, 4}) = min{c12 + f(2, {3, 4}),c13 + f(3, {2, 4}),c14 + f(4, {2, 3})}
= min{2 + 5, 10 + 13, 7 + 22} = 7 (j = 2)
– p. 42/56
Caixeiro viajante - exemplo
f(1, {2, 3, 4}) = min{c12 + f(2, {3, 4}),c13 + f(3, {2, 4}),c14 + f(4, {2, 3})}
= min{2 + 5, 10 + 13, 7 + 22} = 7 (j = 2)
Portanto, um circuito hamiltoniano de custo mínimoé (1, 2, 4, 3, 1) com custo 7.
– p. 42/56
Exercícios
1. Dado um polígono convexo P com vérticesnumerados de 1 a n na ordem cíclica, esuponha que cada diagonal ligando os vérticesi e j possui custo dij. Projete um algoritmo paradeterminar uma triangulação de custo mínimode P .
– p. 43/56
Programacao Dinamica
O problema binário da mochila
– p. 44/56
Problema da Mochila
Dados n objetos com valor e peso associado acada um deles, e uma mochila que suporta pesomáximoW , determinar um subconjunto de objetosde valor máximo e cujo peso não excede W .
– p. 45/56
Problema da Mochila
Dados n objetos com valor e peso associado acada um deles, e uma mochila que suporta pesomáximoW , determinar um subconjunto de objetosde valor máximo e cujo peso não excede W .
Notação:Objetos: x1, x2, . . . , xn
Valores: v1, v2, . . . , vn
Pesos: p1, p2, . . . , pn
Peso da mochila: W
– p. 45/56
Problema da Mochila
Uma solução para o problema da mochila pode serobtida pelo seguinte raciocínio:
“O objeto xn pode estar ou não na solução ótima”
– p. 46/56
Problema da Mochila
Uma solução para o problema da mochila pode serobtida pelo seguinte raciocínio:
“O objeto xn pode estar ou não na solução ótima”
Se o objeto xn estiver na solução ótima, o valordesta solução será vn mais o valor de umasolução ótima do problema da mochila comcapacidadeW " pn e considerando só os n" 1
primeiros itens.
– p. 46/56
Problema da Mochila
Se o objeto xn não estiver na solução ótima, ovalor ótimo será dado pelo valor de umasolução ótima do problema da mochila comcapacidadeW e considerando só os n" 1
primeiros itens.
– p. 47/56
Problema da Mochila
Se o objeto xn não estiver na solução ótima, ovalor ótimo será dado pelo valor de umasolução ótima do problema da mochila comcapacidadeW e considerando só os n" 1
primeiros itens.
Seja f(i, w) o valor ótimo considerando apenas osi primeiros ítens e uma mochila de capacidade w.
– p. 47/56
Problema da Mochila
A recorrência fica então:
f(i, w) =
%f(i" 1, w) se pi > w
max{f(i" 1, w " pi) + vi, f(i" 1, w)} se pi % w
– p. 48/56
Problema da Mochila
A recorrência fica então:
f(i, w) =
%f(i" 1, w) se pi > w
max{f(i" 1, w " pi) + vi, f(i" 1, w)} se pi % w
f(0, w) = 0 e f(i, 0) = 0
– p. 48/56
Problema da Mochila - Exemplo
Peso da mochila = 7Objetos: x1, x2, x3, x4Valores: 10, 7, 25, 24
Pesos: 2, 1, 6, 5
– p. 49/56
Problema da Mochila - Exemplo
Peso da mochila = 7Objetos: x1, x2, x3, x4Valores: 10, 7, 25, 24
Pesos: 2, 1, 6, 5
0 1 2 3 4 5 6 7 w0 0 0 0 0 0 0 0 01 02 03 04 0i
– p. 49/56
Problema da Mochila
Exemplo: Peso da mochila = 7Objetos: x1, x2, x3, x4Valores: 10, 7, 25, 24
Pesos: 2, 1, 6, 5
0 1 2 3 4 5 6 7 w0 0 0 0 0 0 0 0 01 0 0 10 10 10 10 10 102 0 7 10 17 17 17 17 173 0 7 10 17 17 17 25 324 0 7 10 17 17 24 31 34i
– p. 50/56
Problema da Mochila
Qual o tempo gasto pelo algoritmo?
–p. 51/56
Problema da Mochila
Qual o tempo gasto pelo algoritmo? O(n.W )
– p. 51/56
Problema da Mochila
Qual o tempo gasto pelo algoritmo? O(n.W )
Como encontrar uma composição ótima apóscompletada a tabela? Qual o tempo?
–p. 51/56
Exercício1. Resolva o problema da mochila para os valores
Peso da mochila = 15Objetos: x1, x2, x3, x4Valores: 5, 6, 11, 12
Pesos: 3, 5, 6, 7
2. Uma haste de comprimento H precisa ser cortada empequenos pedaços/partes de comprimento{h1, h2, . . . , hn}. Projete um algoritmo para determinarem quais pedaços a haste deve ser cortada de formaque a sobra seja a menor possível.
3. Dada uma coleção A = {a1, a2, . . . , an} de n inteirospositivos que somam N . Projete um algoritmo paradeterminar se existe uma partição de A em doissubconjuntos com a mesma soma.
– p. 52/56
Exercício para pesquisar
4. Considere o seguinte algoritmo guloso para o problemada mochila: a cada passo, escolha o objeto de maiorvalor. Este algoritmo está correto?
– p. 53/56
Exercício5. Problema de investimento de capital:
R$6, 00 unidades de capital disponívelN = 3 atividades diferentes para investimento comganhos dados pelo quadro abaixo:
R g1(R) g2(R) g3(R)
0 0 0 0
1 15 15 26
2 40 40 40
3 80 60 45
4 90 70 50
5 95 73 51
6 100 75 53
Qual o distribuição ótima do recurso?– p. 54/56
Exercício para pesquisar
6. O problema do corte bidimensional guilhotinado: ...(mochila bidimensional)
– p. 55/56
Exercício para pesquisar
1. Árvore de busca binária ótima: Consideremos oproblema de realizar buscas em uma árvore binária debusca contendo os elementos de um conjuntoC = {x1, x2, . . . , xn} (listados em ordem crescente)conhecendo-se as seguintes probabilidades:(a) q0 = Prob. de buscar um elemento x < x1(b) pi = Prob. de buscar o elemento xi(c) qi = Prob. de buscar um elemento xi < x < xi+1
(d) qn = Prob. de buscar um elemento x > xnO problema é construir uma árvore binária de buscaque representa C em que a execução das buscas sejafeita com número mínimo de comparações.
– p. 56/56