1
Programación dinámica
1. Método general.
2. Análisis de tiempos de ejecución.
3. Ejemplos de aplicación.
3.1. Problema del cambio de monedas.
3.2. Problema de la mochila 0/1.
3.3. Multiplicación encadenada de matrices.
2
Método general
La programación dinámica se suele utilizar en problemas de optimización, donde una solución está formada por una serie de decisiones.
Igual que la técnica divide y vencerás, resuelve el problema original combinando las soluciones para subproblemas más pequeños.
Sin embargo, la programación dinámica no utiliza recursividad, sino que almacena los resultados de los subproblemas en una tabla, calculando primero las soluciones para los problemas pequeños.
Con esto se pretende evitar la repetición de cálculos para problemas más pequeños.
3
Método general
Ejemplo. Cálculo de los números de Fibonacci.
Con método recursivo
Fibonacci (n: integer)
Si n< 2 Devolver 1
Sino Devolver Fibonacci (n-1) + Fibonacci (n-2)
Problema: Muchos cálculos están repetidos, tiempo de ejec. exponencial.
Solución: Calcular los valores de menor a mayor empezando por 0, e ir guardando los resultados en una tabla.
Con programación dinámica.
Fibonacci (n: integer)
T[0] = 0; T[1] = 1
para i = 2,3, …,n
T[i] = T[i-1] + T[i-2]
Devolver T[n]
Se utiliza la misma fórmula que en la versión anterior, pero de forma más inteligente. El tiempo de ejecución es ?(n).
4
Método general
Los algoritmos divide y vencerás están dentro de los métodos descendentes.
Empezar con el problema original y descomponer en pasos sucesivos en problemas de menor tamaño.
Partiendo del problema grande, descendemos hacia problemas más sencillos.
La programación dinámica, por el contrario, es un método ascendente:
Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla) y después vamos combinando para resolver los problemas más grandes.
5
Método general
La programación dinámica se basa en el Principio de Optimalidad de Bellman: cualquier subsecuencia de una secuencia óptima debe ser, a su vez, una secuencia óptima.
Para cada problema deberíamos comprobar si es aplicable el principio de optimalidad.
Ejemplo.
2 B 9
A D
3 C 7
Camino óptimo de A a D: A-C-D, de longitud 10
Camino óptimo de A al siguiente nivel: A-B, de longitud 2, y después B-D de longitud 9. Total: A-B-D, de longitud 11
¿Cumple el Principio de Optimalidad?
6
Método general
Aspectos a definir en un algoritmo de programación dinámica:
Ecuación recurrente, para calcular la solución de los problemas grandes en función de los problemas más pequeños.
Determinar los casos base.
Definir las tablas utilizadas por el algoritmo, y cómo son rellenadas.
Cómo se recompone la solución global a partir de los valores de las tablas.
7
Análisis de tiempos de ejecución
El tiempo de ejecución depende de las características concretas del problema a resolver.
En general, será de la forma:
Tamaño de la tabla*Tiempo de rellenar cada elemento de la tabla.
Un aspecto importante de los algoritmos de programación dinámica es que necesitan una tabla para almacenar los resultados parciales, que puede ocupar mucha memoria.
Además, algunos de estos cálculos pueden ser innecesarios.
8
Problema: Dado un conjunto de n tipos de monedas, cada una con valor ci, y dada una cantidad P, encontrar el número mínimo de monedas que tenemos que usar para obtener esa cantidad.
El algoritmo voraz es muy eficiente, pero sólo funciona en un número limitado de casos.
Utilizando programación dinámica:
Definimos el problema en función de problemas más pequeños.
Determinar los valores de los casos base.
Definimos las tablas necesarias para almacenar los resultados de los subproblemas.
Establecemos una forma de rellenar las tablas y de obtener el resultado.
Problema del cambio de monedas
9
Definición de la ecuación recurrente:
Cambio (i, Q), el problema de calcular el número mínimo de monedas necesario para devolver una cantidad Q, usando los i primeros tipos de monedas (es decir los tipos 1…i).
La solución de Cambio(i, Q) puede que utilice k monedas de tipo i o puede que no utilice ninguna.
Si no usa ninguna moneda de ese tipo: Cambio(i, Q) = Cambio(i – 1, Q)
Si usa k monedas de tipo i: Cambio(i, Q) = Cambio(i, Q – k*ci) + k
En cualquier caso, el valor será el mínimo:
Cambio(i, Q) = mink=0,1,…,Q/ci {Cambio(i-1, Q-k* ci)+k}
Casos base: Cambio(i, Q)
Si (i?0) ó (Q< 0) entonces no existe ninguna solución al problema, y Cambio(i, Q) = +?.
En otro caso para cualquier i>0, Cambio(i, 0) = 0.
Problema del cambio de monedas
10
Problema del cambio de monedas
Definición de las tablas utilizadas:
Necesitamos almacenar los resultados de todos los subproblemas.
El problema a resolver será: Cambio (n, P).
Por lo tanto, necesitamos una tabla de nxP, de enteros, que llamaremos D, siendo D[i, j ]= Cambio(i, j).
Ejemplo. n= 3, P= 8, c= (1, 4, 6)
Forma de rellenar las tablas:
De arriba hacia abajo y de izquierda a derecha, aplicar la ecuación de recurrencia:
D[i, j] = mink=0,1,…,Q/ci {D(i-1, Q-k* ci)+k}
11
Problema del cambio de monedas
Algoritmo.
Devolver-cambio (P: int; C: array [1..n] of int; var D: array [1..n, 0..P] of int);
para i = 1,2,…,n
D[i, 0] = 0
para i = 1,2,…,n
para j = 1,2,…,P {Tener en cuenta si el valor }
D[i, j] = mink=0,1,…,Q/ci {D(i-1, Q-k* ci)+k} { cae fuera de la tabla}
Ejemplo. n= 3, P= 8, c= (1, 4, 6)
¿Cuál es el tiempo de ejecución del algoritmo?
¿Cómo es en comparación con el algoritmo voraz?
D[n, P]: número mínimo de monedas que hay que usar para devolver la cantidad P.
12
Problema del cambio de monedas
¿Cómo calcular cuántas monedas de cada tipo deben usarse, es decir la solución (x1, x2, …, xn)?
Se usa otra tabla de decisiones tomadas:
Aux
Algoritmo para obtener una solución:
para i=n,n-1,…,1
xi=Aux[i,P]
P=P-xi*ci
¿Cuál es el tiempo de ejecución del algoritmo para obtener la solución?
¿Es aplicable el principio de optimalidad?
0
1
2
3
4
5
6
7
8
C
1
= 1
0
1
2
3
4
5
6
7
8
C
2
= 4
0
0
0
0
1
1
1
1
2
C
3
= 6
0
0
0
0
0
0
1
1
0
Página siguiente  |