116
An´ alise de Algoritmos Programação Dinâmica – p. 1/56

Análise de Algoritmos - Programação Dinâmica

Embed Size (px)

Citation preview

Page 1: Análise de Algoritmos - Programação Dinâmica

Analise de Algoritmos

Programação Dinâmica

–p. 1/56

Page 2: Análise de Algoritmos - Programação Dinâmica

Programação Dinâmica

Aplicável a problemas de otimização

– p. 2/56

Page 3: Análise de Algoritmos - Programação Dinâmica

Programação Dinâmica

Aplicável a problemas de otimização

Combina soluções de subproblemas

–p. 2/56

Page 4: Análise de Algoritmos - Programação Dinâmica

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

Page 5: Análise de Algoritmos - Programação Dinâmica

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

Page 6: Análise de Algoritmos - Programação Dinâmica

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

Page 7: Análise de Algoritmos - Programação Dinâmica

Programacao Dinamica

Multiplicação de matrizes

–p. 4/56

Page 8: Análise de Algoritmos - Programação Dinâmica

Multiplicação de matrizes

Problema: Multiplicar n matrizes

M = M1 !M2 ! · · ·!Mn

realizando o número mínimo de operações

– p. 5/56

Page 9: Análise de Algoritmos - Programação Dinâmica

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

Page 10: Análise de Algoritmos - Programação Dinâmica

Multiplicação de matrizes

As matrizes são multiplicadas aos pares

– p. 6/56

Page 11: Análise de Algoritmos - Programação Dinâmica

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

Page 12: Análise de Algoritmos - Programação Dinâmica

Multiplicação de matrizes

Exemplo: M = M1 !M2 !M3 !M4 comb = {200, 2, 30, 20, 5}.

– p. 7/56

Page 13: Análise de Algoritmos - Programação Dinâmica

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

Page 14: Análise de Algoritmos - Programação Dinâmica

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

Page 15: Análise de Algoritmos - Programação Dinâmica

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

Page 16: Análise de Algoritmos - Programação Dinâmica

Multiplicação de matrizes

Como determinar uma sequência ótima demultiplicação?

–p. 9/56

Page 17: Análise de Algoritmos - Programação Dinâmica

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

Page 18: Análise de Algoritmos - Programação Dinâmica

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

Page 19: Análise de Algoritmos - Programação Dinâmica

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

Page 20: Análise de Algoritmos - Programação Dinâmica

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

Page 21: Análise de Algoritmos - Programação Dinâmica

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

Page 22: Análise de Algoritmos - Programação Dinâmica

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

Page 23: Análise de Algoritmos - Programação Dinâmica

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

Page 24: Análise de Algoritmos - Programação Dinâmica

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

Page 25: Análise de Algoritmos - Programação Dinâmica

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

Page 26: Análise de Algoritmos - Programação Dinâmica

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

Page 27: Análise de Algoritmos - Programação Dinâmica

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

Page 28: Análise de Algoritmos - Programação Dinâmica

Multiplicação de matrizes

Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1

– p. 15/56

Page 29: Análise de Algoritmos - Programação Dinâmica

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

Page 30: Análise de Algoritmos - Programação Dinâmica

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

Page 31: Análise de Algoritmos - Programação Dinâmica

Multiplicação de matrizes

Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1

– p. 16/56

Page 32: Análise de Algoritmos - Programação Dinâmica

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

Page 33: Análise de Algoritmos - Programação Dinâmica

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

Page 34: Análise de Algoritmos - Programação Dinâmica

Multiplicação de matrizes

Mij = min{Mik+Mk+1,j+ bi"1bkbj}, k = i, . . . , j"1

– p. 17/56

Page 35: Análise de Algoritmos - Programação Dinâmica

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

Page 36: Análise de Algoritmos - Programação Dinâmica

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

Page 37: Análise de Algoritmos - Programação Dinâmica

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

Page 38: Análise de Algoritmos - Programação Dinâmica

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

Page 39: Análise de Algoritmos - Programação Dinâmica

Programacao Dinamica

Maior subsequência comum

–p. 19/56

Page 40: Análise de Algoritmos - Programação Dinâmica

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

Page 41: Análise de Algoritmos - Programação Dinâmica

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

Page 42: Análise de Algoritmos - Programação Dinâmica

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

Page 43: Análise de Algoritmos - Programação Dinâmica

LCS – Algoritmo força bruta

Para cada subsequência de X, verifique se elaé subsequência de Y .

– p. 22/56

Page 44: Análise de Algoritmos - Programação Dinâmica

LCS – Algoritmo força bruta

Para cada subsequência de X, verifique se elaé subsequência de Y .

Qual o tempo?

–p. 22/56

Page 45: Análise de Algoritmos - Programação Dinâmica

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

Page 46: Análise de Algoritmos - Programação Dinâmica

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

Page 47: Análise de Algoritmos - Programação Dinâmica

LCS – Algoritmo força bruta

Podemos fazer melhor?

– p. 23/56

Page 48: Análise de Algoritmos - Programação Dinâmica

LCS – Algoritmo força bruta

Podemos fazer melhor?Sim, utilizando programação dinâmica.

– p. 23/56

Page 49: Análise de Algoritmos - Programação Dinâmica

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

Page 50: Análise de Algoritmos - Programação Dinâmica

Maior subsequência comum

Uma LCS(X,Y ) pode ser obtida recursivamenteda seguinte forma:

– p. 24/56

Page 51: Análise de Algoritmos - Programação Dinâmica

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

Page 52: Análise de Algoritmos - Programação Dinâmica

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

Page 53: Análise de Algoritmos - Programação Dinâmica

Maior subsequência comum

Defina c(i, j) como o tamanho da LCS(Xi, Yj).

– p. 25/56

Page 54: Análise de Algoritmos - Programação Dinâmica

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

Page 55: Análise de Algoritmos - Programação Dinâmica

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

Page 56: Análise de Algoritmos - Programação Dinâmica

Maior subsequência comum

Vamos calcular LCS(X,Y ), ondeX = ABCB e Y = BDCAB.

– p. 26/56

Page 57: Análise de Algoritmos - Programação Dinâmica

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

Page 58: Análise de Algoritmos - Programação Dinâmica

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

Page 59: Análise de Algoritmos - Programação Dinâmica

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

Page 60: Análise de Algoritmos - Programação Dinâmica

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

Page 61: Análise de Algoritmos - Programação Dinâmica

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

Page 62: Análise de Algoritmos - Programação Dinâmica

Maior subsequência comum

Qual o tempo gasto pelo algoritmo?

–p. 31/56

Page 63: Análise de Algoritmos - Programação Dinâmica

Maior subsequência comum

Qual o tempo gasto pelo algoritmo? O(m.n)

– p. 31/56

Page 64: Análise de Algoritmos - Programação Dinâmica

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

Page 65: Análise de Algoritmos - Programação Dinâmica

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

Page 66: Análise de Algoritmos - Programação Dinâmica

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

Page 67: Análise de Algoritmos - Programação Dinâmica

Programacao Dinamica

O problema do caixeiro viajante

–p. 34/56

Page 68: Análise de Algoritmos - Programação Dinâmica

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

Page 69: Análise de Algoritmos - Programação Dinâmica

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

Page 70: Análise de Algoritmos - Programação Dinâmica

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

Page 71: Análise de Algoritmos - Programação Dinâmica

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

Page 72: Análise de Algoritmos - Programação Dinâmica

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

Page 73: Análise de Algoritmos - Programação Dinâmica

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

Page 74: Análise de Algoritmos - Programação Dinâmica

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

Page 75: Análise de Algoritmos - Programação Dinâmica

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

Page 76: Análise de Algoritmos - Programação Dinâmica

Caixeiro viajante

Os valores de f necessários para resolver o PCVpodem ser obtidos em ordem crescente de |C|, daseguinte forma:

– p. 39/56

Page 77: Análise de Algoritmos - Programação Dinâmica

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

Page 78: Análise de Algoritmos - Programação Dinâmica

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

Page 79: Análise de Algoritmos - Programação Dinâmica

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

Page 80: Análise de Algoritmos - Programação Dinâmica

Caixeiro viajante - exemplo

1

110

2 77

121

59 3

15

20

3

2 4

– p. 40/56

Page 81: Análise de Algoritmos - Programação Dinâmica

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

Page 82: Análise de Algoritmos - Programação Dinâmica

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

Page 83: Análise de Algoritmos - Programação Dinâmica

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

Page 84: Análise de Algoritmos - Programação Dinâmica

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

Page 85: Análise de Algoritmos - Programação Dinâmica

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

Page 86: Análise de Algoritmos - Programação Dinâmica

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

Page 87: Análise de Algoritmos - Programação Dinâmica

Caixeiro viajante - exemplo

f(2, {3, 4}) = min{c23 + f(3, {4}), c24 + f(4, {3})}

– p. 41/56

Page 88: Análise de Algoritmos - Programação Dinâmica

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

Page 89: Análise de Algoritmos - Programação Dinâmica

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

Page 90: Análise de Algoritmos - Programação Dinâmica

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

Page 91: Análise de Algoritmos - Programação Dinâmica

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

Page 92: Análise de Algoritmos - Programação Dinâmica

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

Page 93: Análise de Algoritmos - Programação Dinâmica

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

Page 94: Análise de Algoritmos - Programação Dinâmica

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

Page 95: Análise de Algoritmos - Programação Dinâmica

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

Page 96: Análise de Algoritmos - Programação Dinâmica

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

Page 97: Análise de Algoritmos - Programação Dinâmica

Programacao Dinamica

O problema binário da mochila

– p. 44/56

Page 98: Análise de Algoritmos - Programação Dinâmica

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

Page 99: Análise de Algoritmos - Programação Dinâmica

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

Page 100: Análise de Algoritmos - Programação Dinâmica

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

Page 101: Análise de Algoritmos - Programação Dinâmica

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

Page 102: Análise de Algoritmos - Programação Dinâmica

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

Page 103: Análise de Algoritmos - Programação Dinâmica

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

Page 104: Análise de Algoritmos - Programação Dinâmica

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

Page 105: Análise de Algoritmos - Programação Dinâmica

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

Page 106: Análise de Algoritmos - Programação Dinâmica

Problema da Mochila - Exemplo

Peso da mochila = 7Objetos: x1, x2, x3, x4Valores: 10, 7, 25, 24

Pesos: 2, 1, 6, 5

– p. 49/56

Page 107: Análise de Algoritmos - Programação Dinâmica

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

Page 108: Análise de Algoritmos - Programação Dinâmica

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

Page 109: Análise de Algoritmos - Programação Dinâmica

Problema da Mochila

Qual o tempo gasto pelo algoritmo?

–p. 51/56

Page 110: Análise de Algoritmos - Programação Dinâmica

Problema da Mochila

Qual o tempo gasto pelo algoritmo? O(n.W )

– p. 51/56

Page 111: Análise de Algoritmos - Programação Dinâmica

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

Page 112: Análise de Algoritmos - Programação Dinâmica

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

Page 113: Análise de Algoritmos - Programação Dinâmica

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

Page 114: Análise de Algoritmos - Programação Dinâmica

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

Page 115: Análise de Algoritmos - Programação Dinâmica

Exercício para pesquisar

6. O problema do corte bidimensional guilhotinado: ...(mochila bidimensional)

– p. 55/56

Page 116: Análise de Algoritmos - Programação Dinâmica

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