Ejercicios Programacion Dinamica

Programación dinámica
Introducción
El problema de la mochila 0-1
Camino de coste mínimo en
un grafo multietapa
Multiplicación de una secuencia
de matrices
Comparaciones de secuencias
Caminos mínimos entre todos
los pares de nodos de un grafo
Árboles binarios de búsqueda
óptimos
Un problema de fiabilidad
de sistemas
El problema del viajante
de comercio
Planificación de trabajosUna competición internacional
Triangulación de polígonos
J. Campos - C.P.S.

2
7
17
30
40
47
53
64
69
79
92
98

Esquemas algorítmicos - Programación dinámicaPág. 1

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 unbeneficio bixi.
– El objetivo es llenar la mochila, de capacidad C,
de manera que se maximice el beneficio.
maximizar
sujeto a

∑ bi xi

1≤i ≤n

∑ pi xi ≤ C

1≤i ≤n

con 0 ≤ x i ≤ 1, bi > 0, pi > 0, 1 ≤ i ≤ n

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.

J. Campos - C.P.S.

Esquemas algorítmicos - Programación dinámicaPág. 2

Programación dinámica:
Introducción
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), conbeneficio 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.

J. Campos - C.P.S.

Esquemas algorítmicos - Programación dinámicaPág. 3

Programación dinámica:
Introducción
R. Bellman: Dynamic Programming,
Princeton University Press, 1957.

Técnica de programacióndiná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 decisionesde una secuencia óptima de decisiones
que resuelve un problema
también debe ser óptima respecto al
subproblema que resuelve.”

J. Campos - C.P.S.

Esquemas algorítmicos - Programación dinámicaPág. 4

Programación dinámica:
Introducción
– Supongamos que un problema se resuelve tras
tomar un secuencia d1, d2, …, dn de decisiones.
– Si hay d opciones posibles para cada una de lasdecisiones, 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ásgrandes.

J. Campos - C.P.S.

Esquemas algorítmicos - Programación dinámicaPág. 5

Programación dinámica:
Introducción
Más formalmente:
– Sea E0 el estado inicial del problema.
– Sea D1 = {v 11 ,K,v 1n 1 } el conjunto de valores de
decisión posibles para la decisión d1.
– Sea E1i el estado del problema tras la elección del
valor v1i, 1≤i≤n1.
– Sea S1i una secuencia óptima dedecisiones
respecto al estado E1i.
Principio de optimalidad de Bellman:
Una secuencia óptima de decisiones
respecto a E0 es la mejor de las secuencias de
decisión {v1i,S1i}, 1≤i≤n1.
El mismo razonamiento puede aplicarse a
cualquier subsecuencia de decisiones
dk, …, dl, 1≤k≤l≤n, partiendo como estado
inicial de Ek-1.
Una solución dinámica para este problema,
simbolizado como (k,l), debe...