PDF de programación - Tema 4 Programación dinámica - Parte I. Estructuras de Datos

Programa de teoría
Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

Parte II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D.

Tema 4. Programación dinámica.

1

PARTE II: ALGORÍTMICA

Tema 4. Programación dinámica.

4.1. Método general.
4.2. Análisis de tiempos de ejecución.
4.3. Ejemplos de aplicación.

4.3.1. Problema de la mochila 0/1.
4.3.2. Problema del cambio de monedas.

A.E.D.

Tema 4. Programación dinámica.

2

1

4.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).

A.E.D.

Tema 4. Programación dinámica.

3

4.1. Método general.

• Ejemplo. Cálculo de los números de Fibonacci.

F(n) =

1
F(n-1) + F(n-2)

Si 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]

A.E.D.

Tema 4. Programación dinámica.

4

2

4.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: Θ(n)
• Con divide y vencerás:

F(n)F(n)

F(n-1)
F(n-1)

F(n-2)
F(n-2)

F(n-2)
F(n-2)

F(n-3)
F(n-3)

F(n-3)
F(n-3)

F(n-4)
F(n-4)

F(n-3) F(n-4)
F(n-3)

F(n-4) F(n-4)

F(n-4) F(n-5)

F(n-5) F(n-4)

F(n-4) F(n-5)

F(n-5) F(n-5)

F(n-5) F(n-6)
F(n-6)

– Problema: Muchos cálculos están repetidos.
– El tiempo de ejecución es exponencial: Θ(1,62n)
5

A.E.D.

Tema 4. Programación dinámica.

4.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.

A.E.D.

Tema 4. Programación dinámica.

6

3

4.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) =

C[i, j]
min(Dk-1(i, j), Dk-1(i, k) + Dk-1(k, j))

Si k=0
Si k>0

Dn(i, j) → caminos mínimos finales

A.E.D.

Tema 4. Programación dinámica.

7

4.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 el

Principio de optimalidad de Bellman:

La solución óptima de un problema se obtiene

combinando soluciones óptimas de subproblemas.

A.E.D.

Tema 4. Programación dinámica.

8

4

4.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.

A.E.D.

Tema 4. Programación dinámica.

9

4.1. Método general.

Pasos para aplicar programación dinámica:

1) Obtener una descomposición recurrente del

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”...

A.E.D.

Tema 4. Programación dinámica.

10

5

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.

4.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.

A.E.D.

Tema 4. Programación dinámica.

11

4.2. Análisis de tiempos de ejecución.
• 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.

A.E.D.

Tema 4. Programación dinámica.

12

6

4.3. Ejemplos de aplicación.
4.3.1. Problema de la mochila 0/1.

• Como el problema de la mochila, pero los objetos no se

pueden partir (se cogen enteros o nada).

• 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.

• Formulación matemática:

Maximizar Σ xi bi; sujeto a la restricción Σ xi pi ≤ M, y xi∈{0,1}

i=1..n

i=1..n

A.E.D.

Tema 4. Programación dinámica.

13

4.3.1. Problema de la mochila 0/1.

• Ejemplo: n = 4; M = 7

b = (2, 3, 4, 5)
p = (1, 2, 3, 4)

4 kg

7 Kg.

3 kg

2 kg

PVP 5

PVP 4

PVP 3

1 kg

PVP 2

• ¿Qué solución devuelve el algoritmo voraz para el

problema de la mochila?

• ¿Qué solución devuelve el algoritmo voraz adaptado al

caso 0/1 (o se coge un objeto entero o no)?

• ¿Cuál es la solución óptima?
• Ojo: el problema es un NP-completo clásico.

A.E.D.

Tema 4. Programación dinámica.

14

7

4.3.1. Problema de la mochila 0/1.

• Ejemplo: n = 2; M = 100

b = (2, 190)
p = (1, 100)

100 Kg.

100 kg

1 kg

PVP 2

PVP 190

• ¿Qué solución devuelve el algoritmo voraz para el

problema de la mochila?

• ¿Qué solución devuelve el algoritmo voraz adaptado al

caso 0/1 (o se coge un objeto entero o no)?

• ¿Cuál es la solución óptima?
A.E.D.

Tema 4. Programación dinámica.

15

4.3.1. Problema de la mochila 0/1.
• Aplicamos programación dinámica al problema...

Paso 1)
• ¿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).

• ¿Coger o no coger un objeto?

Resolver(1..n)

Coger n + Resolver(1..n-1)

No coger n + Resolver(1..n-1)
A.E.D.

16

Tema 4. Programación dinámica.

8

4.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): entero

Problema 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.

A.E.D.

Tema 4. Programación dinámica.

17

4.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?

A.E.D.

Tema 4. Programación dinámica.

18

9

4.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

Mochila(k, m) = -∞

max {Mochila(k-1, m), bk + Mochila(k-1, m-pk)}

Si k=0 ó m=0
Si k<0 ó m<0

• ¿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.

A.E.D.

Tema 4. Programación dinámica.

19

4.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 -∞.

A.E.D.

Tema 4. Programación dinámica.

20

10

4.3.1. Proble