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.

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

A.E.D.

Tema 4. Programación dinámica.

13

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.

14

7

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.

15

4.3.1. Problema de la mochila 0/1.

• Casos base:

– Si m o k son negativos, el problema es irresoluble:

• Resultado. La siguiente ecuación obtiene la solución

Mochila(k, m) = -∞

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

16

8

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.

17

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

A.E.D.

Tema 4. Programación dinámica.

18

9

4.3.1. Problema de la mochila 0/1.

• Ejemplo. n= 3, M= 6, p= (2, 3, 4), b= (1, 2, 5)

i

V
0

1

2

3

0

0

0

0

0

1

0

0

0

0

2

0

1

1

1

j
3

0

1

2

2

4

0

1

2

5

5

0

1

3

5

6

0

1

3

6

• ¿Cuánto es el orden de complejidad del algoritmo?

A.E.D.

Tema 4. Programación dinámica.

19

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

xi:= 1

– Si V[i, j] = V[i-1, j-pi] + bi, entonces sí se usa el objeto i

– Si se cumplen ambas, entonces podemos usar el objeto i

o no (existe más de