Programación dinámica: Introducción
Recordemos el problema de la mochila:
Se tienen n objetos fraccionables y una mochila.
El objeto i tiene peso pi y una fracción xi (0=xi=1) del objeto i produce un beneficio bixi.
El objetivo es llenar la mochila, de capacidad C, de manera que se maximice el beneficio.
Una variante: la “mochila 0-1”
xi sólo toma valores 0 ó 1, indicando que el objeto se deja fuera o se mete en la mochila.
Los pesos, pi, y la capacidad son números naturales. Los beneficios, bi, son reales no negativos.
Ejemplo:
n=3 C=15
(b1,b2,b3)=(38,40,24)
(p1,p2,p3)=(9,6,5)
Recordar la estrategia voraz:
Tomar siempre el objeto que proporcione mayor beneficio por unidad de peso.
Se obtiene la solución:
(x1,x2,x3)=(0,1,1), con beneficio 64
Sin embargo, la solución óptima es:
(x1,x2,x3)=(1,1,0), con beneficio 78
Por tanto, la estrategia voraz no calcula la solución óptima del problema de la mochila 0-1.
Programación dinámica: Introducción
Técnica de programación dinámica
Se emplea típicamente para resolver problemas de optimización.
Permite resolver problemas mediante una secuencia de decisiones.
Como el esquema voraz
A diferencia del esquema voraz, se producen varias secuencias de decisiones y sólamente al final se sabe cuál es la mejor de ellas.
Está basada en el principio de optimalidad de Bellman:
“Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema también debe ser óptima respecto al subproblema que resuelve.”
Programación dinámica: Introducción
R. Bellman: Dynamic Programming,
Princeton University Press, 1957.
Supongamos que un problema se resuelve tras tomar un secuencia d1, d2, …, dn de decisiones.
Si hay d opciones posibles para cada una de las decisiones, una técnica de fuerza bruta exploraría un total de dn secuencias posibles de decisiones (explosión combinatoria).
La técnica de programación dinámica evita explorar todas las secuencias posibles por medio de la resolución de subproblemas de tamaño creciente y almacenamiento en una tabla de las soluciones óptimas de esos subproblemas para facilitar la solución de los problemas más grandes.
Programación dinámica: Introducción
Sea mochila(k,l,P) el problema:
El problema de la mochila 0-1 es mochila(1,n,C).
El problema de la mochila 0-1
Ecuación de recurrencia hacia adelante:
Si es el beneficio (o ganancia total) de una solución óptima de mochila(j,n,c), entonces
dependiendo de que el objeto j-ésimo entre o no en la solución (nótese que sólo puede entrar si c-pj=0).
Además,
El problema de la mochila 0-1
Ambas ecuaciones permiten calcular ,
que es el valor de una solución óptima de
mochila(1,n,C).
(Nótese que la ecuación de recurrencia es
hacia adelante pero el cálculo se realiza hacia atrás.)
v
g
j
(
c
)
v
g
j
(
c
)
?
max
v
g
j
?
1
(
c
)
,
v
g
j
?
1
(
c
?
p
j
)
?
b
j
?
?
(Gp:)
(Gp:)
(Gp:)
(Gp:) v
(Gp:) g
(Gp:) n
(Gp:) ?
(Gp:) 1
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:) ?
(Gp:) 0
(Gp:) ,
(Gp:)
(Gp:) para cualquier capacidad
(Gp:) c
Ecuación de recurrencia hacia atrás:
Si es el beneficio (o ganancia total) de una solución óptima de mochila(1,j,c), entonces
dependiendo de que el objeto j-ésimo entre o no en la solución (nótese que sólo puede entrar si c-pj=0).
Además,
El problema de la mochila 0-1
Ambas ecuaciones permiten calcular ,
que es el valor de una solución óptima de
mochila(1,n,C).
(Ahora la recurrencia es hacia atrás pero el cálculo
se realiza hacia adelante.)
(Gp:)
(Gp:)
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:)
(Gp:)
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:) ?
(Gp:) max
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) ?
(Gp:) 1
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:) ,
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) ?
(Gp:) 1
(Gp:) (
(Gp:) c
(Gp:) ?
(Gp:) p
(Gp:) j
(Gp:) )
(Gp:) ?
(Gp:) b
(Gp:) j
(Gp:) ?
(Gp:) ?
(Gp:)
(Gp:)
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) 0
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:) ?
(Gp:) 0
(Gp:) ,
(Gp:)
(Gp:) para cualquier capacidad
(Gp:) c
Tanto la recurrencia hacia adelante como hacia atrás permiten escribir un algoritmo recursivo de forma inmediata.
El problema de la mochila 0-1
función mochila1(p,b:vector[1..n] de nat;
C:nat) devuelve nat
principio
devuelve g(n,C)
fin
función g(j,c:nat) devuelve nat
principio
si j=0 entonces devuelve 0
sino
si c
Problema: ineficiencia
Un problema de tamaño n se reduce a dos subproblemas de tamaño (n-1).
Cada uno de los dos subproblemas se reduce a otros dos…
Por tanto, se obtiene un algoritmo exponencial.
Sin embargo, el número total de sub-problemas a resolver no es tan grande:
La función tiene dos parámetros:
el primero puede tomar n valores distintos y
el segundo, C valores.
¡Luego sólo hay nC problemas diferentes!
Por tanto, la solución recursiva está generando y resolviendo el mismo problema muchas veces.
El problema de la mochila 0-1
(Gp:)
(Gp:)
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) (
(Gp:) c
(Gp:) )
Para evitar la repetición de cálculos, las soluciones de los subproblemas se deben almacenan en una tabla.
Matriz n?C cuyo elemento (j,c) almacena
Para el ejemplo anterior:
n=3 C=15
(b1,b2,b3)=(38,40,24)
(p1,p2,p3)=(9,6,5)
El problema de la mochila 0-1
(Gp:)
(Gp:)
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:)
(Gp:)
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:) ?
(Gp:) max
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) ?
(Gp:) 1
(Gp:) (
(Gp:) c
(Gp:) )
(Gp:) ,
(Gp:)
(Gp:) w
(Gp:) g
(Gp:) j
(Gp:) ?
(Gp:) 1
(Gp:) (
(Gp:) c
(Gp:) ?
(Gp:) p
(Gp:) j
(Gp:) )
(Gp:) ?
(Gp:) b
(Gp:) j
(Gp:) ?
(Gp:) ?
El problema de la mochila 0-1
algoritmo mochila(ent p,b:vect[1..n]de nat;
ent Cap:nat;
sal g:vect[0..n,0..Cap]de nat)
variables c,j:nat
principio
para c:=0 hasta Cap hacer g[0,c]:=0 fpara;
para j:=1 hasta n hacer g[j,0]:=0 fpara;
para j:=1 hasta n hacer
para c:=1 hasta Cap hacer
si c
Cálculos posibles a partir de la tabla g:
beneficio total: g[n,Cap]
los objetos metidos en la mochila:
El problema de la mochila 0-1
algoritmo objetos(ent p,b:vect[1..n]de nat;
ent Cap:nat;
ent g:vect[0..n,0..Cap]de nat)
principio
test(n,Cap)
fin
algoritmo test(ent j,c:nat)
principio
si j>0 entonces
si cg[j-1,c]
entonces
test(j-1,c-p[j]);
escribir('meter ',j)
sino test(j-1,c)
fsi
fsi
fsi
fin
Consideraciones finales
Cada componente de la tabla g se calcula en tiempo constante, luego el coste de construcción de la tabla es O(nC).
El algoritmo test se ejecuta una vez por cada valor de j, desde n descendiendo hasta 0, luego su coste es O(n).
Si C es muy grande, entonces esta solución no es buena.
Si los pesos pi o la capacidad C son reales, esta solución no sirve.
El problema de la mochila 0-1
Camino de coste mínimo en un grafo multietapa
Grafo multietapa:
Un grafo multietapa G=(V,A) es un grafo dirigido en el que se puede hacer una partición del conjunto V de vértices en k (k=2) conjuntos distintos Vi, 1=i=k, tal que todo arco del grafo (u,v) es tal que u?Vi y v?Vi+1 para algún i, 1=i