Descenso del río - programación dinámica

Metodolog´ y Tecnolog´ de la Programaci´n ıa ıa o Ingenier´ T´cnica en Inform´tica de Sistemas ıa e a Curso 2008-2009 Esquemas algor´ ıtmicos. Programaci´n din´mica o a
Yolanda Garc´ Ruiz ıa Jes´s Correas u D228 D228 ygarciar@fdi.ucm.es jcorreas@fdi.ucm.es

Departamento de Sistemas Inform´ticos y Computaci´n a o Universidad Complutense de Madrid (elaborado a partir de [GV00], [BB97] y notas deS. Est´vez y R. e Gonz´lez del Campo) a
Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u 1 / 48

Bibliograf´ ıa

Importante: Estas transparencias son un material de apoyo a las clases presenciales y no sustituyen a la bibliograf´ b´sica ni a las ıa a propias clases presenciales para el estudio de la asignatura Bibliograf´ b´sica: ıa a
[GV00]: cap´ ıtulo 5 [BB97]: cap´ ıtulo 8

Ejerciciosresueltos:
[MOV04]: cap´ ıtulo 13

Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u

2 / 48

Esquemas algor´ ıtmicos. Programaci´n din´mica o a

1 2 3 4 5 6 7 8 9

Caracter´ ısticas generales de la programaci´n din´mica o a Ejemplo: N´meros de Fibonacci u Coeficientes Binomiales Devolver el cambio Problema de la mochila 0-1 Descenso del r´ ıo Algoritmo de Floyd Multiplicaci´n encadenada dematrices o Programaci´n din´mica y recursi´n. Funciones con memoria o a o

Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u

3 / 48

Caracter´ ısticas generales de la programaci´n din´mica o a

En el esquema Divide y Vencer´s vimos una serie de problemas cuyas a soluciones se pueden representar mediante la subdivisi´n en o subproblemas Los subproblemas deb´ ser independientes ıan En casocontrario, la complejidad de los algoritmos es exponencial, por la repetici´n de c´lculos o a El objetivo de la programaci´n din´mica consiste en resolver los o a subproblemas una sola vez, guardando las soluciones obtenidas hasta el momento en una tabla

Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u

4 / 48

Caracter´ ısticas generales de la programaci´n din´mica o a (cont.)
Podemoscomparar la programaci´n din´mica con otros m´todos: o a e Divide y vencer´s: a
El m´todo Divide y vencer´s es un m´todo descendente, de e a e refinamiento progresivo La programaci´n din´mica es una t´cnica ascendente, que soluciona de o a e forma iterativa problemas t´ ıpicamente recursivos

Algoritmos voraces:
Los algoritmos voraces buscan la soluci´n al problema mediante un o conjunto de etapas yuna elecci´n voraz o La programaci´n din´mica resuelve un caso a partir de otros de menor o a tama˜o, y aplica el principio de optimalidad n

Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u

5 / 48

Ejemplo: los n´meros de Fibonacci u
La expresi´n matem´tica de la funci´n de Fibonacci es la siguiente o a o (n ∈ N): 1 si n < 2 Fib(n) = Fib(n − 1) + Fib(n − 2) si n ≥ 2 Si implementamos unalgoritmo recursivo de esta definici´n, el o resultado es muy ineficiente (O(2n )) Podemos comprobar que la ineficiencia se debe a que se producen llamadas repetidas para calcular el resultado de la funci´n. o Por ejemplo: Fib(5) = Fib(4) + Fib(3) = Fib(3) + Fib(2) + Fib(2) + Fib(1) = ...
Fib(4) Fib(3)

Yolanda Garc´ Jes´s Correas (DSIC - UCM) ıa, u

6 / 48

Ejemplo: los n´meros de Fibonacci(cont.) u
Podemos almacenar los resultados intermedios en una tabla: Fib(0) Fib(1) Fib(2) ··· Fib(n)

Un algoritmo iterativo que calcula la sucesi´n de Fibonacci puede ser el o siguiente: fun FibIter1(n) crear tabla[0..n] si n≤1 entonces return n si no tabla[0] ← 0 ; tabla[1] ← 1 desde i← 2 hasta n hacer tabla[i] ← tabla[i-1]+tabla[i-2] fin desde devolver tabla[n] fin si fin fun
Yolanda Garc´ Jes´sCorreas (DSIC - UCM) ıa, u

La complejidad temporal de este algoritmo es lineal La complejidad espacial tambi´n e ¿C´mo podr´ mejorarse este o ıa algoritmo?

7 / 48

Caracter´ ısticas generales de la programaci´n din´mica o a (cont.)
El t´rmino programaci´n din´mica fue utilizado inicialmente en la e o a d´cada de 1940 para resolver problemas de optimizaci´n matem´tica e o a En este...