1. Método general. La base de la programación
dinámica es el razonamiento inductivo: ¿cómo
resolver un problema combinando soluciones para problemas
más pequeños? La idea es la misma que en divide y
vencerás… pero aplicando una estrategia distinta.
Similitud: Descomposición recursiva del problema. Se
obtiene aplicando un razonamiento inductivo. Diferencia: Divide y
vencerás: aplicar directamente la fórmula recursiva
(programa recursivo). Programación dinámica:
resolver primero los problemas más pequeños,
guardando los resultados en una tabla (programa iterativo).
1. Método general. Ejemplo. Cálculo de los
números de Fibonacci. 1 Si n = 2 F(n-1) + F(n-2) Si n >
2 Con divide y vencerás. operación Fibonacci (n:
entero): entero si n=2 entonces devolver 1 sino devolver
Fibonacci(n-1) + Fibonacci(n-2) Con programación
dinámica. operación Fibonacci (n: entero): entero
T[1]:= 1; T[2]:= 1 para i:= 3, …, n hacer T[i]:= T[i-1] +
T[i-2] devolver T[n] F(n) =
1. Método general. Los dos usan la misma fórmula
recursiva, aunque de forma distinta. ¿Cuál es
más eficiente? Con programación dinámica:
T(n) Con divide y vencerás: Problema: Muchos
cálculos están repetidos. El tiempo de
ejecución es exponencial: T(1,62n) (Gp:) F(n-2) (Gp:)
F(n-3) (Gp:) F(n-4) (Gp:) F(n-1) (Gp:) F(n-2) (Gp:) F(n) (Gp:)
F(n-3) (Gp:) F(n-3) (Gp:) F(n-4) (Gp:) F(n-4) (Gp:) F(n-5) (Gp:)
F(n-4) (Gp:) F(n-5) (Gp:) F(n-5) (Gp:) F(n-6)
1. Método general. Métodos ascendentes y
descendentes Métodos descendentes (divide y
vencerás) Empezar con el problema original y descomponer
recursivamente en problemas de menor tamaño. Partiendo del
problema grande, descendemos hacia problemas más
sencillos. Métodos ascendentes (programación
dinámica) Resolvemos primero los problemas pequeños
(guardando las soluciones en una tabla). Después los vamos
combinando para resolver los problemas más grandes.
Partiendo de los problemas pequeños avanzamos hacia los
más grandes.
1. Método general. Ejemplo. Algoritmo de Floyd, para
calcular los caminos mínimos entre cualquier par de nodos
de un grafo. Razonamiento inductivo: para calcular los caminos
mínimos pudiendo pasar por los k primeros nodos usamos los
caminos mínimos pasando por los k-1 primeros. Dk(i, j):
camino mínimo de i a j pudiendo pasar por los nodos 1, 2,
…, k. Dk(i, j) = Dn(i, j) ? caminos mínimos finales
C[i, j] Si k=0 min(Dk-1(i, j), Dk-1(i, k) + Dk-1(k, j)) Si
k>0
1. Método general. Ejemplo. Algoritmo de Floyd.
Aplicación de la fórmula: Empezar por el problema
pequeño: k = 0 Avanzar hacia problemas más grandes:
k = 1, 2, 3, … ¿Cómo se garantiza que un
algoritmo de programación dinámica obtiene la
solución correcta? Una descomposición es correcta
si cumple elPrincipio de optimalidad de Bellman: La
solución óptima de un problema se obtiene
combinando soluciones óptimas de subproblemas.
1. Método general. O bien: cualquier subsecuencia de una
secuencia óptima debe ser, a su vez, una secuencia
óptima. Ejemplo. Si el camino mínimo de A a B pasa
por C, entonces los trozos de camino de A a C, y de C a B deben
ser también mínimos. Ojo: el principio no siempre
es aplicable. Contraejemplo. Si el camino simple más largo
de A a B pasa por C, los trozos de A a C y de C a B no tienen por
qué ser soluciones óptimas.
1. Método general. Pasos para aplicar programación
dinámica: Obtener una descomposición recurrente del
problema: – Ecuación recurrente. – Casos base. 2) Definir
la estrategia de aplicación de la fórmula: – Tablas
utilizadas por el algoritmo. – Orden y forma de rellenarlas. 3)
Especificar cómo se recompone la solución final a
partir de los valores de las tablas. Punto clave: obtener la
descomposición recurrente. Requiere mucha
“creatividad”…
1. Método general. Cuestiones a resolver en el
razonamiento inductivo: ¿Cómo reducir un problema a
subproblemas más simples? ¿Qué
parámetros determinan el tamaño del problema (es
decir, cuándo el problema es “más
simple”)? Idea: ver lo que ocurre al tomar una
decisión concreta ? interpretar el problema como un
proceso de toma de decisiones. Ejemplos. Floyd. Decisiones: Pasar
o no pasar por un nodo intermedio. Mochila 0/1. Decisiones: coger
o no coger un objeto dado.
La programación dinámica se basa en el uso de
tablas donde se almacenan los resultados parciales. En general,
el tiempo será de la forma: Tamaño de la
tabla*Tiempo de rellenar cada elemento de la tabla. Un aspecto
importante es la memoria puede llegar a ocupar la tabla.
Además, algunos de estos cálculos pueden ser
innecesarios. 2. Análisis de tiempos de
ejecución.
3.1. Problema de la mochila 0/1. Datos del problema: n:
número de objetos disponibles. M: capacidad de la mochila.
p = (p1, p2, …, pn) pesos de los objetos. b = (b1, b2, …, bn)
beneficios de los objetos. ¿Cómo obtener la
descomposición recurrente? Interpretar el problema como un
proceso de toma de decisiones: coger o no coger cada objeto.
Después de tomar una decisión particular sobre un
objeto, nos queda un problema de menor tamaño (con un
objeto menos). 3. Ejemplos de aplicación.
3.1. Problema de la mochila 0/1. ¿Coger o no coger un
objeto k? Si se coge: tenemos el beneficio bk, pero en la mochila
queda menos espacio, pk. Si no se coge: tenemos el mismo problema
pero con un objeto menos por decidir. ¿Qué
varía en los subproblemas? Número de objetos por
decidir. Peso disponible en la mochila. Ecuación del
problema. Mochila(k, m: entero): enteroProblema de la mochila
0/1, considerando sólo los k primeros objetos (de los n
originales) con capacidad de mochila m. Devuelve el valor de
beneficio total.
3.1. Problema de la mochila 0/1. Definición de Mochila(k,
m: entero): entero Si no se coge el objeto k:Mochila(k, m) =
Mochila(k – 1, m) Si se coge:Mochila(k, m) = bk + Mochila(k – 1,
m – pk) Valor óptimo: el que dé mayor beneficio:
Mochila(k, m) = max { Mochila(k – 1, m), bk + Mochila(k – 1, m –
pk) } Casos base: Si m=0, no se pueden incluir objetos:
Mochila(k, 0) = 0 Si k=0, tampoco se pueden incluir: Mochila(0,
m) = 0 ¿Y si m o k son negativos?
3.1. Problema de la mochila 0/1. Casos base: Si m o k son
negativos, el problema es irresoluble: Mochila(k, m) = -?
Resultado. La siguiente ecuación obtiene la
solución óptima del problema: 0 Si k=0 ó m=0
Mochila(k, m) = -? Si k<0 ó m<0 max {Mochila(k-1,
m), bk + Mochila(k-1, m-pk)} ¿Cómo aplicarla de
forma ascendente? Usar una tabla para guardar resultados de los
subprob. Rellenar la tabla: empezando por los casos base, avanzar
a tamaños mayores.
3.1. Problema de la mochila 0/1. Paso 2) Definición de las
tablas y cómo rellenarlas 2.1) Dimensiones y tamaño
de la tabla Definimos la tabla V, para guardar los resultados de
los subproblemas: V[i, j] = Mochila(i, j) La solución del
problema original es Mochila(n, M). Por lo tanto, la tabla debe
ser:V: array [0..n, 0..M] de entero Fila 0 y columna 0: casos
base de valor 0. Los valores que caen fuera de la tabla son casos
base de valor -?.
3.1. Problema de la mochila 0/1. 2.2) Forma de rellenar las
tablas: Inicializar los casos base:V[i, 0]:= 0; V[0, j]:= 0 Para
todo i desde 1 hasta n Para todo j desde 1 hasta M, aplicar la
ecuación: V[i, j]:= max (V[i-1, j], bi + V[i-1, j-pi]) El
beneficio óptimo es V[n, M] Ojo: si j-pi es negativo,
entonces es el caso -?, y el máximo será siempre el
otro término.
3.1. Problema de la mochila 0/1. Ejemplo. n= 3, M= 6, p= (2, 3,
4), b= (1, 2, 5) i j ¿Cuánto es el orden de
complejidad del algoritmo?
3.1. Problema de la mochila 0/1. Paso 3) Recomponer la
solución óptima V[n, M] almacena el beneficio
óptimo, pero ¿cuál son los objetos que se
cogen en esa solución? Obtener la tupla solución
(x1, x2, …, xn) usando V. Idea: partiendo de la posición
V[n, M], analizar las decisiones que se tomaron para cada objeto
i. Si V[i, j] = V[i-1, j], entonces la solución no usa el
objeto i ? xi:= 0 Si V[i, j] = V[i-1, j-pi] + bi, entonces
sí se usa el objeto i ? xi:= 1 Si se cumplen ambas,
entonces podemos usar el objeto i o no (existe más de una
solución óptima).
3.1. Problema de la mochila 0/1. 3) Cómo recomponer la
solución óptima j:= P para i:= n, …, 1 hacer si
V[i, j] == V[i-1, j] entonces x[i]:= 0 sino // V[i, j] == V[i-1,
j-pi] + bi x[i]:= 1 j:= j – pi finsi finpara Aplicar sobre
el ejemplo anterior.
3.1. Problema de la mochila 0/1. ¿Cuánto
será el tiempo de recomponer la solución?
¿Cómo es el tiempo en relación al algoritmo
de backtracking y al de ramificación y poda?
¿Qué pasa si multiplicamos todos los pesos por
1000? ¿Se cumple el principio de optimalidad?
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: 1) Definir el problema en
función de problemas más pequeños 2) Definir
las tablas de subproblemas y la forma de rellenarlas 3)
Establecer cómo obtener el resultado a partir de las
tablas 3.2. Problema del cambio de monedas.
3.2. Problema del cambio de monedas. 1) Descomposición
recurrente del problema Interpretar como un problema de toma de
decisiones. ¿Coger o no coger una moneda de tipo k? Si se
coge: usamos 1 más y tenemos que devolver cantidad ck
menos. Si no se coge: tenemos el mismo problema pero descartando
la moneda de tipo k. ¿Qué varía en los
subproblemas? Tipos de monedas a usar. Cantidad por devolver.
Ecuación del problema. Cambio(k, q: entero):
enteroProblema del cambio de monedas, considerando sólo
los k primeros tipos, con cantidad a devolver q. Devuelve el
número mínimo de monedas necesario.
3.2. Problema del cambio de monedas. Definición de
Cambio(k, q: entero): entero Si no se coge ninguna moneda de tipo
k:Cambio(k, q) = Cambio(k – 1, q) Si se coge 1 moneda de tipo
k:Cambio(k, q) = 1 + Cambio(k, q – ck) Valor óptimo: el
que use menos monedas: Cambio(k, q) = min { Cambio(k – 1, q), 1 +
Cambio(k, q – ck) } Casos base: Si q=0, no usar ninguna moneda:
Cambio(k, 0) = 0 En otro caso, si q<0 ó k=0, no se
puede resolver el problema: Cambio(q, k) = +?
3.2. Problema del cambio de monedas. Ecuación recurrente:
0 Si q=0 Cambio(k, q) = -? Si q<0 ó k=0 min
{Cambio(k-1, q), 1 + Cambio(k, q-ck)} 2) Aplicación
ascendente mediante tablas Matriz D ? D[i, j] = Cambio(i, j) D:
array [1..n, 0..P] de entero para i:= 1, …, n hacer D[i, 0]:= 0
para i:= 1, …, n hacer para j:= 0, …, P hacer D[i, j]:=
min(D[i-1, j], 1+D[i, j-ci]) devolver D[n, P] Ojo si cae fuera de
la tabla.
3.2. Problema del cambio de monedas. Ejemplo. n= 3, P= 8, c= (1,
4, 6) i j ¿Cuánto es el orden de complejidad del
algoritmo? ¿Cómo es en comparación con el
algoritmo voraz?
3.2. Problema del cambio de monedas. 3) Cómo recomponer la
solución a partir de la tabla ¿Cómo calcular
cuántas monedas de cada tipo deben usarse, es decir, la
tupla solución (x1, x2, …, xn)? Analizar las decisiones
tomadas en cada celda, empezando en D[n, P]. ¿Cuál
fue el mínimo en cada D[i, j]? D[i – 1, j] ? No utilizar
ninguna moneda más de tipo i. D[i, j – C[i]] + 1 ? Usar
una moneda más de tipo i. Implementación: x: array
[1..n] de entero ? x[i] = número de monedas usadas de tipo
i
3.2. Problema del cambio de monedas. 3) Cómo recomponer la
solución a partir de la tabla x:= (0, 0, …, 0) i:= n j:=
P mientras (i?0) AND (j?0) hacer si D[i, j] == D[i-1, j] entonces
i:= i – 1 sino x[i]:= x[i] + 1 j:= j – ci finsi
finmientras ¿Qué pasa si hay varias soluciones
óptimas? ¿Y si no existe ninguna solución
válida?
Programación dinámica. Conclusiones El razonamiento
inductivo es una herramienta muy potente en resolución de
problemas. Aplicable no sólo en problemas de
optimización. ¿Cómo obtener la
fórmula? Interpretar el problema como una serie de toma de
decisiones. Descomposición recursiva no necesariamente
implica implementación recursiva. Programación
dinámica: almacenar los resultados en una tabla, empezando
por los tamaños pequeños y avanzando hacia los
más grandes.