adfad

dasfdasfdasfdadf
adfadfadf
adfaeqegaerg
234125123454123
fqrefqewfqwerqewtqrefdddddddddddddddddddddddddddddddddddeeee-
eeeeeeeee
hhhhhhhhhhhhhhhhhhhhhh
rrrrrrrrrrrrrrrrrrrrrrr
wwwwwwwwwwwwwwwww
kjllllllllllllllllllllllllllllllllllk



















































lkjlkjlkjlkjlñkjlñkj












































































22222222222222222222222221111111111122222222222





















erqeqrqer










rqerq






















faeaefa
dffrJ. Campos - C.P.S. Esquemas algorítmicos - Programación dinámicaPág. 1
Programación dinámica
􀂙 Introducción 2
􀂙 El problema de la mochila 0-1 7
􀂙 Camino de coste mínimo en
un grafo multietapa 17
􀂙 Multiplicación de una secuencia
de matrices 30
􀂙 Comparaciones de secuencias 40
􀂙 Caminos mínimos entre todos
los pares de nodos de un grafo 47
􀂙Árboles binarios de búsqueda
óptimos 53
􀂙 Un problema de fiabilidad
de sistemas 64
􀂙 El problema del viajante
de comercio 69
􀂙 Planificación de trabajos 79
􀂙 Una competición internacional 92
􀂙 Triangulación de polígonos 98
J. Campos - C.P.S. Esquemas algorítmicos - Programación dinámicaPág. 2
Programación dinámica:
Introducción
􀂙 Recordemos el problema de la mochila:
– Se tienen nobjetos 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úmerosnaturales.
Los beneficios, bi, son reales no negativos.
maximizar bixi
1≤i ≤n
Σ
sujeto a pixi
1≤i ≤n
Σ ≤ C
con 0 ≤ xi ≤ 1, bi > 0, pi > 0, 1 ≤ i ≤ n
J. Campos - C.P.S. Esquemas algorítmicos - Programación dinámicaPág. 3
􀂙 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 depeso.
– 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
J. Campos - C.P.S. Esquemas algorítmicos - Programación dinámicaPág. 4
􀂙 Técnica de programación dinámica
– Seemplea 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...