programacion dinamica

12/07/2015

1

COMPANYLOGOTcnicas Algortmicas

Programacin dinmica

J. C. Carbajal L.

Inconveniente de Divide & Vencer1

Calculo de los nmeros de Fibonacci2

Problema multiplicacin de matrices3

Subsecuencia comn ms larga4

D.A.I. A l g o r i t m i c a I I I

5

COMPANYLOGOInconveniente de Divide & Vencer

Algunas veces puede ser ineficiente

Nmeros de Fibonacci: F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 para n > 1

Secuencia is 0, 1, 1, 2, 3, 5, 8, 13,

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOCalculo de los nmeros de Fibonacci

Obvio algoritmo recursivo:

Fib(n): if n = 0 1 then returna n else returna (F(n-1) + Fib(n-2))


COMPANYLOGOrbol de recursin para Fib(5)


Fib(5)

Fib(4)

Fib(3)

Fib(3)

Fib(2) Fib(2) Fib(1)

Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)

Fib(1) Fib(0)

COMPANYLOGOCuntas llamadas recursivas?

Si todas las hojas tienen la misma profundidad, entonces habra aproximadamente 2n llamadas recursivas.

Pero esto termine el conteo.

Sin embargo con el conteo ms cuidadoso se puede demostrar que es ((1.6)n)

An exponencial!


COMPANYLOGOGuardar Trabajo

Enfoque derrochador - repetir el trabajo innecesariamente

Fib (2) se calcula tres veces

En su lugar, calcular Fib (2) una vez, almacenar el resultado en una tabla, y acceder a ella cuando sea necesario.


12/07/2015

2

COMPANYLOGOMs eficiente que el alg. recursivo


F[0] := 0; F[1] := 1; F[n] := Fib(n); Fib(n):

if n = 0 1 then returna F[n] if F[n-1] = NIL then F[n-1] := Fib(n-1) if F[n-2] = NIL then F[n-2] := Fib(n-2) returna (F[n-1] + F[n-2])

Calcula cada F[i] slo una vez

COMPANYLOGOEjemplo de memoized Fib


1

0

NIL

NIL

NIL

NIL

F0

1

2

3

4

5

1

2

3

5

Fib(5)

Fib(4)

Fib(3)

Fib(2) retorna 0+1 = 1

rellena F[2] con 1,

retorna 1+1 = 2

rellena F[3] con 2,

retorna 2+1 = 3

rellena F[4] con 3,

retorna 3+2 = 5

COMPANYLOGOCmo deshacerse de la recursividad

La recursividad implica una sobrecarga

tiempo adicional para las llamadas de funcin

espacio extra para almacenar la informacin en la pila de tiempo de ejecucin de cada llamada a la funcin activa en ese momento

Evitar la sobrecarga de recursividad rellenando las entradas de la tabla de abajo hacia arriba, en lugar de arriba hacia abajo.


COMPANYLOGOSubproblemas dependencias

Averiguar que subproblemas se basan en que otros subproblemas

ejemplo:


F0 F1 F2 F3 Fn-2 Fn-1 Fn

COMPANYLOGO

Orden de computacin de los subproblemas

Luego de averiguar un orden para el clculo de los subproblemas que respeten las dependencias:

cuando se te plantea un subproblema, ya ha resuelto todos los subproblemas de la que depende

Ejemplo: Slo solucionar en el orden

F0 , F1 , F2 , F3 ,


COMPANYLOGOSolucin PD para Fibonacci


Fib(n): F[0] := 0; F[1] := 1; for i := 2 to n do

F[i] := F[i-1] + F[i-2]

return F[n]

Puede realizar optimizaciones de aplicacin especfica por ejemplo, ahorrar espacio por slo

mantener los ltimos dos nmeros calculados

12/07/2015

3

COMPANYLOGO

Problema Producto encadenado de matrices


Multiplicar matrices no cuadradas:A es n x m, B es m x pAB es n x p cuyo estrada (i,j) es aik bkj

Calcular AB toma nmp multiplicacionesescalares y n(m-1)p sumas escalares(usando el algoritmo bsico).

Supongamos que tenemos una secuencia de matrices a multiplicar. Cul es el mejor orden?

debe ser igual

Multiplicacin encadenada de matrices

COMPANYLOGOPor qu importa el Orden

Suponga que tenemos 4 matrices:A, 30 x 1 B, 1 x 40 C, 40 x 10D, 10 x 25

((AB)(CD)) : requiere 41,200 mults. (A((BC)D)) : requiere 1400 mults.

Producto encadenado de matricesCalcular A=A0*A1**An-1

Ai es di di+1Problema: Cmo agrupar (poner parntesis)?


COMPANYLOGOMultiplicacin de n matrices

M=M1xM2x xMnDebido a la propiedad asociativa del producto de matrices, puede hacer la multiplicacin de muchas formas. Queremos determinar la que minimiza el nmero de operaciones necesarias. Por ejemplo: las dimensiones de A es de 13x5, B de 5x89, C de 89x3 y D de 3x34. Tenemos:

((AB)C)D requiere 10582 multiplicaciones.13x5x89 + 13x89x3 + 13x3x34 = 5785 + 3471 + 1326

(AB)(CD) requiere 54201 multiplicaciones13x5x89 + 89x3x34 + 13x89x34 = 5785 + 9078 + 39338

(A(BC))D requiere 2856 multiplicaciones. A((BC)D) requiere 4055 multiplicaciones. A(B(CD)) requiere 26418 multiplicaciones.


COMPANYLOGO

Problema Producto encadenado de n matrices

Dada las matrices A1, A2, , An, donde Ai esdi-1 x di:

[1] Cul es el nmero mnimo de multiplicaciones escalares requerida para calcular A1 A2 An?

[2] Qu orden de multiplicaciones de matrices alcanza este mnimo?

Tarea: revisar como hacer el caso [2]


COMPANYLOGOUna posible solucin

Pruebe todas las posibilidades y escoger la mejor opcin.

Inconveniente es que hay demasiados de ellos (exponencial en el nmero de matrices a ser multiplicadas)

Necesidad de ser ms inteligente - tratar programacin dinmica!


COMPANYLOGOPaso 1: Desarrollar una solucin recursiva

Definir M(i,j) para ser el mnimo nmero de multiplicaciones necesarias para calcular Ai Ai+1 Aj

Meta: Hallar M(1,n).

Base: M(i,i) = 0.

Recursin: Cmo definir M (i, j) de forma recursiva?


12/07/2015

4

COMPANYLOGODefinir M(i, j) recursivamente

Considere todas las formas posibles de dividir Aitravs de Aj en dos pedazos.

Comparar los costos de todas estas divisiones:

mejor coste caso para calcular el producto de las dos piezas

ms el costo de la multiplicacin de los dos productos

Tome la mejor

M(i,j) = mink(M(i,k) + M(k+1,j) + di-1dkdj)


COMPANYLOGODefinir M(i, j) recursivamente


(Ai Ak)(Ak+1 Aj)

P1 P2

mnimo costo para calcular P1 es M(i,k)

mnimo costo para calcular P2 es M(k+1,j)

costo para calcular P1 P2 es di-1dkdj

COMPANYLOGO

Paso 2: Encuentre las dependencias entre subproblemas


1 2 3 4 5

1 0

2 n/a 0

3 n/a n/a 0

4 n/a n/a n/a 0

5 n/a n/a n/a n/a 0

META!

M:

calcular el cuadro rojo requiere de los azules: a la izquierda y abajo.

COMPANYLOGODefinir las dependencia

Calcular M(i,j) usa todo en la misma fila de la izquierda:

M(i,i), M(i,i+1), , M(i,j-1) y todo en la misma columna a continuacin:

M(i,j), M(i+1,j),,M(j,j)


COMPANYLOGO

Paso 3: Identificar el Orden para resolver subproblemas

Recordemos las dependencias entre los subproblemas slo se encuentran

Resolver los subproblemas (es decir, llenar las entradas de la tabla) de esta manera:

ir a lo largo de la diagonal

empezar justo por encima de la diagonal principal

terminar en la esquina superior derecha (meta)


COMPANYLOGOOrden para resolver subproblemas


1 2 3 4 5

1 0

2 n/a 0

3 n/a n/a 0

4 n/a n/a n/a 0

5 n/a n/a n/a n/a 0

M:

12/07/2015

5

COMPANYLOGOPseudocdigo


for i := 1 to n do M[i,i] := 0

for d := 1 to n-1 do // diagonales

for i := 1 to n-d to // filas w/ una entrada sobre la d-sima diagonal

j := i + d // columna correspondinte a fila i en d-sima diagonal

M[i,j] := infinity

for k := 1 to j-1 to

M[i,j] := min(M[i,j], M[i,k]+M[k+1,j]+di-1dkdj)

endfor

endfor

endforTiempo ejecucin O(n3)

prestar atencin aqu

recordar secuencia

real de multiplicacions.

COMPANYLOGOEjemplo


M: 1 2 3 4

1 0 1200 700 1400

2 n/a 0 400 650

3 n/a n/a 0 10,000

4 n/a n/a n/a 0

1: A es 30x1

2: B es 1x40

3: C es 40x10

4: D es 10x25

COMPANYLOGOSeguimiento del Orden

Est bien saber el costo del orden ms barato, pero cul es ese orden ms barato?

Mantenga otra matriz S y actualizarlo cuando se calcula el costo mnimo en el bucle interno

Una vez que M y S se han llenado, entonces llamar a un algoritmo recursivo en S para imprimir el orden actual


COMPANYLOGOPseudocdigo modificado


for i := 1 to n do M[i,i] := 0

for d := 1 to n-1 do // diagonales

for i := 1 to n-d to // filas w/ una entrada sobre la d-sima diagonal

j := i + d // columna correspondinte a fila i en d-sima diagonal

M[i,j] := infinity

for k := 1 to j-1 to

M[i,j] := min(M[i,j], M[i,k]+M[k+1,j]+di-1dkdj)

if lnea previa cambio el valor de M[i,j] then S[i,j] := kendfor

endfor

endfor

llevar un registro de punto de divisin ms barato

encontrado hasta ahora: entre Ak y Ak+1

COMPANYLOGOEjemplo


M: 1 2 3 4

1 0 1200 700 1400

2 n/a 0 400 650

3 n/a n/a 0 10,000

4 n/a n/a n/a 0

1: A es 30x1

2: B es 1x40

3: C es 40x10

4: D es 10x25

1

2

3

1

3

1S:

COMPANYLOGOEjemplo: Cadenas de longitud 1


1 2 3 4

1 0

2 0

3 0

4 0

A1 301

A2 140

A3 4010

A4 1025

ij

12/07/2015

6



A1 301

A2 140

A3 4010

A4 1025

1 2 3 4

1 0 12001

2 0 4002

3 0 100003

4 0

ij

m[1,2]=m[1,1]+m[2,2]+30x1+x40=1200m[2,3]=m[2,2]+m[3,3]+1x40+x10=400m[3,4]=m[3,3]+m[4,4]+40x10+x25=10000



A1 301

A2 140

A3 4010

A4 1025

1 2 3 4

1 0 12001

700

1

2 0 4002

650

3

3 0 100003

4 0

ij

1,3 = 1,1 + 2,3 + 30 1 10 = 700 1,2 + 3,3 + 30 40 10 = 13200

2,4 = 2,2 + 3,4 + 1 40 25 = 1100 2,3 + 4,4 + 1 10 25 = 650



A1 301

A2 140

A3 4010

A4 1025

1 2 3 4

1 0 12001

700

1

1400

1

2 0 4002

650

3

3 0 100003

4 0

ij

1,4 = 1,1 + 2,4 + 30 1 25 = 1400 1,2 + 3,4 + 30 40 25 = 41200 1,3 + 4,4 + 30 10 25 = 8200

COMPANYLOGOUsar S para imprimir el mejor orden

Llamar a Print(S, 1, n) para obtener todo el ordenamiento.

Print(S,i,j):

if i = j then salida "A" + i //+ es una cadena concat

else

k := S[i,j]

salida "(" + Print(S,i,k) + Print(S,k+1,j) + ")"


COMPANYLOGOEjemplo


S: 1 2 4

1 n/a 1 1 1

2 n/a n/a 2 3

3 n/a n/a n/a 3

4 n/a n/a n/a n/a

COMPANYLOGOSubsecuencia comn ms larga

Otro ejemplo de programacin dinmica

Dado dos cadenas X = [x1, x2 ,, xm] y

Y = [y1, y2, , yn]

Encontrar la subsecuencia comn mas larga (SCL) de X eY no necesariamente contiguas!

Ejemplo: X = [A, B, C, B, D, A, B]

Y = [B, D, C, A, B, A]

una SCL es [B, C, B, A]

otra SCL ess [B, D, A, B]


12/07/2015

7

COMPANYLOGOSolucin de fuerza bruta

Tome una de las cadenas, por ejemplo X

Considere cada posible subsecuencia de X

Compruebe si esa subsecuencia aparece en Y

Tomara tiempo exponencial, ya que hay 2m

posibles subsecuencias de X

para cada uno de los m caracteres en X, hay dos opciones (est en la subsecuencia o no est)


COMPANYLOGOExpresin recursiva para la solucin

Se C[i,j] la longitud de SCL de Xi = [x1, , xi] y

Yj = [y1, , yj]

Meta: C[m,n]

Base: C[0,j] = 0 (Xi esta vaca) para todo j

C[I,0] = 0 (Yj esta vaca) para todo I

i rango desde 0 hasta m, j rango desde 0 hasta n



Formula ra C[i,j]:

Case 1: xi = yj. Recursivamente encontrar la SCL de Xi-1 e Yj-1 y

adjuntar xiAs C[i,j] = C[i-1,j-1] + 1 if i > 0, j > 0, e xi = yj


xi

yj

igual

Xi-1

Yj-1


Caso 2: xi yj. Recursivamente encontrar SCL de Xi-1 e YjRecursivamente encontrar SCL de Xi e Yj-1Tomar el ms largo

As C[i,j] = max{C[i,j-1], C[i-1,j]} if i > 0, j > 0, and xi yj


xi

yj

No es igual

Xi-1

Yj-1

COMPANYLOGO

Determinar dependencia entre subproblemas

C[i,j] depende de C[i-1,j-1], C[i-1,j], y C[i,j-1]


0 1 j-1 j n01

i-1i

Goal

COMPANYLOGO

Determinar el orden para la solcucin de los subproblemas

Un orden para resolver los subproblemas (es decir, el llenado de la matriz) que respete las dependencias es la fila de mayor orden:

hacer las filas de arriba hacia abajo

dentro de cada fila, ir de izquierda a derecha


12/07/2015

8

COMPANYLOGOPseudocdigo

rellenar la fila 0 todo con 0

rellenar la columna 0 todo con 0

para cada fila desde 1 hasta m hacer

para cada columna desde 1 hasta n hacer

rellenar C[i,j] de acuerdo con la frmula


COMPANYLOGOComplejidad en tiempo

Hay O(mn) subproblemas (entradas en el arreglo).

Cada subproblema toma el tiempo de computo de O(1).

El tiempo total es O(mn).


COMPANYLOGOCalculo de la subsecuencia actual

Lleve un registro de la entrada de la tabla vecina que da la solucin ptima a un subproblema: arriba, a la izquierda, o diagonal

vnculos de ruptura arbitrariamente

Utilice otra matriz 2-D, b, para obtener esta informacin. guardar en b[i,j] if xi = yj (este carcter es parte de una

subsecuencia comn)

guardar en b[i,j] if SCL de Xi e Yj-1 fue mayor

guardar en b[i,j] if SCL de Xi-1 e Yj fue mayor

Seguir la pista hacia atras desde b[m,n] hasta llegar a un borde Cada vez es encontrado, se aade el carcter correspondiente

a la subsecuencia comn ms larga que est construyendo


COMPANYLOGOAlgoritmo de SCL-Length

SCL-Length(X, Y)

1. m = length(X) // obtiene # de smbolos de X

2. n = length(Y) // obtiene # de smbolos de Y

3. for i = 1 to m c[i,0] = 0 // caso especial: Y04. for j = 1 to n c[0,j] = 0 // caso especial : X05. for i = 1 to m // para todo Xi6. for j = 1 to n // para todo Yj7. if ( Xi == Yj )

8. c[i,j] = c[i-1,j-1] + 1

9. else c[i,j] = max( c[i-1,j], c[i,j-1] )

10. return c


COMPANYLOGOEjemplo para SCL


Veremos como el algoritmo SCL trabajacon el siguiente ejemplo:

X = ABCB

Y = BDCAB

SCL(X, Y) = BCB

X = A B C B

Y = B D C A B

Cul es el subsecuencia comn ms larga de X e Y?

COMPANYLOGOEjemplo SCL (0)


j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

X = ABCB; m = |X| = 4Y = BDCAB; n = |Y| = 5Asignar al array c[5,4]

ABCB

BDCAB

12/07/2015

9



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

for i = 1 to m c[i,0] = 0 for j = 1 to n c[0,j] = 0

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1

else c[i,j] = max( c[i-1,j], c[i,j-1] )

0

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


0 0 0

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


0 0 0 1

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


000 1 1

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


0 0 10 1

1

ABCB

BDCAB

12/07/2015

10



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

1 1 11

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

1 1 1 1 2

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

21 1 11

1 1

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

1 21 11

1 1 2

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

1 21 1

1 1 2

1

22

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

1 21 1

1 1 2

1

22

1

ABCB

BDCAB

12/07/2015

11



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

1 21 1

1 1 2

1

22

1 1 2 2

ABCB

BDCAB



j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

B

Yj BB ACD

0

0

00000

0

0

0

if ( Xi == Yj )c[i,j] = c[i-1,j-1] + 1


1000 1

1 21 1

1 1 2

1

22

1 1 2 2 3

ABCB

BDCAB

COMPANYLOGOComo encontrar SCL real


Hasta ahora, slo hemos encontrado la longitud de SCL, pero no la propia SCL.

Queremos modificar este algoritmo para que produzca sub secuencia comn ms larga de X e Y

Cada c [i, j] depende de c [i-1, j] y C [i, j-1] o c [i-1, j-1]

Para cada c [i, j] nosotros podemos decir cmo fue adquirida:

2

2 3

2 Por ejemplo, aqui

c[i,j] = c[i-1,j-1] +1 = 2+1=3

COMPANYLOGOComo encontrar SCL real


Recordar que

, = 1, 1 + 1 = ,

max( , 1 , 1, )

As que podemos empezar de c [m, n] e ir hacia atrs

Siempre que c [i, j] = c [i-1, j-1] +1, recuerda x [i] (porque x [i] es una parte de SCL)

Cuando i = 0 j = 0 (es decir, llegamos al principio), salida recordada, letras en orden inverso

COMPANYLOGOEncontrar SCL


j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

Yj BB ACD

0

0

00000

0

0

0

1000 1

1 21 1

1 1 2

1

22

1 1 2 2 3B

COMPANYLOGOEncontrar SCL (2)


j 0 1 2 3 4 5

0

1

2

3

4

i

Xi

A

B

C

Yj BB ACD

0

0

00000

0

0

0

1000 1

1 21 1

1 1 2

1

22

1 1 2 2 3B

B C BSCL (orden inverso):

SCL (orden directo): B C B(esta cadena result ser un palndromo)

programacion dinamica

Documents