Programación dinámica

La recursividad múltiple implica que una función se llama a si misma varias veces (no solamente una vez). Un ejemplo es la función que calcula el n-ésimo número de la serie Fibonacci:


int fibonacci(int n) {
   if (n <= 1) return 1;
   else return fibonacci(n - 1) + fibonacci(n - 2);
}

Estudiamos qué pasa cuando llamamos a la función fibonacci con n=4:

fibonacci(4) fibonacci(3) fibonacci(2) fibonacci(1) => return 1 fibonacci(0) => return 1 fibonacci(1) => return 1 fibonacci(2) fibonacci(1) => return 1 fibonacci(0) => return 1

La llamada a fibonacci con n=4 recursivamente llama a fibonacci con n=3 y n=2, respectivamente. A su vez, estas llamadas generan otras llamadas recursivas, hasta llegar a un caso base (n=0 o n=1).

En particular, observamos que la función fibonacci se llama múltiples veces con n=2. Esto es ineficiente: una vez calculado el resultado para n=2, no necesitamos calcularlo de nuevo. En este caso el efecto es dramático: el número de veces que se hace la llamada fibonacci(2) es exponencial en el n inicial.

La idea de la programación dinámica es sencilla: una vez calculada la solución a un subproblema, se guarda en memoria para evitar calcular el mismo resultado varias veces.

Memoization

La estrategia más intuitiva para recordar resultados calculados es definir una estructura de memoria externa a la función, y aprovecharla dentro de la función para recordar resultados. Esta estrategia se llama memoización ("memoization" en inglés, no a confundir con "memorization"). En el caso de la serie Fibonacci el código sería el siguiente:


vector<int> res(100, -1); // inicializar el resultado a -1
res[0] = res[1] = 1;      // establecer los casos base

int fibonacci(int n) { if (res[n] > 0) return res[n]; else return res[n] = fibonacci(n - 1) + fibonacci(n - 2); }

La primera vez que se llama a fibonacci con n=2, el valor de res[2] es -1 (el valor inicial). Por lo tanto, no se cumple la condición del if, por lo que recursivamente se llama a fibonacci con n=1 y n=0, respectivamente. Para n=1 y n=0, el valor de res[n] es 1, que es mayor que 0, por lo que directamente se devuelve. La suma fibonacci(1)+fibonacci(0) = 1+1 = 2 se guarda en res[2] y se devuelve.

La siguiente vez que se llama a fibonacci con n=2, el valor de res[2] es 2, por lo que se cumple la condición del if. Como consecuencia se devuelve 2 directamente sin llamar recursivamente a fibonacci con n=1 y n=0.

Con esta modificación la complejidad del algoritmo disminuye de exponencial a lineal, lo que significa un ahorro enorme de tiempo. (Para la serie Fibonacci existe un algoritmo que calcula el n-ésimo número en tiempo logarítmico, que es mucho más rápido todavía.)

Programación dinámica

Uno podría pensar que la memoización es la manera más conveniente de resolver un problema de recursividad múltiple. Sin embargo, una función recursiva gasta un poco de memoria y tiempo en cada llamada recursiva. Por esta razón, la programación dinámica prescinde de la recursividad y resuelve el problema exclusivamente con la iteración.

La idea es llenar el vector o matriz de resultados de abajo arriba, empezando por los casos base. Al resolver un subproblema se aplica la misma idea recursiva para obtener el resultado. Sin embargo, si los subproblemas recursivos ya han sido resueltos no es necesario hacer ninguna llamada recursiva, sino que el resultado se puede calcular directamente a partir de los resultados guardados en memoria.

Veamos como calcular el n-ésimo número en la serie Fibonacci con la programación dinámica. Igual que antes declaramos un vector donde se guardarán los resultados.


vector<int> res(100, -1); // inicializar el resultado a -1
res[0] = res[1] = 1;      // establecer los casos base

for (int n = 2; n <= 10; ++n)
   res[n] = res[n-2] + res[n-1];

La línea dentro del bucle corresponde a la misma idea recursiva que la función recursiva original: el n-ésimo número de la serie es igual a la suma de los dos números anteriores. Estos números se pueden recuperar directamente del vector res, ya que el bucle ya habrá pasado por n-2 y n-1, por lo que los resultados de estos subproblemas ya estarán guardados.

Fibonacci recursivo: fibo1.cpp
Fibonacci con memoización: fibo2.cpp
Fibonacci con programación dinámica: fibo3.cpp

Problema de la moneda

El denominado "problema de la moneda" es el siguiente: dados diferentes tipos de monedas, cada uno con un valor diferente, y una cantidad C, ¿cuál es el menor número de monedas necesarias para devolver el cambio C?

Para las monedas del sistema monetario del euro existe una estrategia básica para resolver el problema:

  1. Coge una moneda con el valor V más grande tal que V <= C
  2. Repite desde 1 con el valor C - V hasta que C = 0

Sin embargo, esta estrategia no funciona para valores aleatorios de las monedas. Por ejemplo, si las monedas tienen valores 1, 4 y 6, el número mínimo de monedas para hacer un cambio de 8 es 2 monedas de 4 (cogiendo una moneda de 6 necesitamos como mínimo 3 monedas en total).

En general, para resolver el problema de la moneda tenemos que probar todas las posibles combinaciones de coger monedas. Para la cantidad C, las posibilidades son: coger una moneda del primer tipo, coger una moneda del segundo tipo, etc. En cada caso se genera un subproblema del mismo tipo por resolver. Por ejemplo, si cogemos una moneda de valor 1, recursivamente tenemos que encontrar la mejor manera de devolver el cambio C-1, y sumarle 1 para obtener una posible solución para C. La solución para C es la mejor entre todas estas posibles maneras de coger la primera moneda.

Si denominamos A(C) el subproblema para la cantidad C, una definición resursiva para el problema es:

A(0) = 0 (si la cantidad es 0 no necesitamos ninguna moneda)
A(C) = min(1 + A(C-m_1), 1 + A(C-m_2), ..., 1 + A(C-m_k))

donde k es el número total de monedas y m_i es el valor de la moneda i. Ahora podemos escribir una solución basada en la programación dinámica:


int M[3] = {1, 4, 6};  // tipos de moneda diferentes
int A[100001];
A[0] = 0;
for (int C = 1; C <= 100000; ++C) {
   A[C] = 1000000000; // número grande para empezar
   for (int i = 0; i < 3; ++i)
      if (M[i] <= C && 1 + A[C-M[i]] < A[C])
         A[C] = 1 + A[C-M[i]];
}

Después del bucle el array A contendrá el resultado para cada C en el rango [0, 100000].

Código para el problema de la moneda: moneda.cpp

Resolver un problema con la programación dinámica

En general los pasos necesarios para resolver un problema con la programación dinámica son las siguientes:

  1. Encontrar una definición recursiva para el problema (incluyendo los casos base)
  2. Inicializar la estructura de memoria (normalmente un vector o una matriz)
  3. Llenar el resultado para los casos base
  4. Usar bucles para calcular el resultado para otros casos, empleando la definición recursiva

La clave es encontrar una definición recursiva correcta, o sea el paso 1.

Problemas para resolver esta semana

Sencillos:

UVa logo 10285 - Longest Run on a Snowboard
UVa logo 10069 - Distinct Subsequences
UVa logo 10651 - Pebble Solitaire
OIE logo Coeficientes binomiales
OIE logo Escape del laberinto
OIE logo Cardgame

Avanzados:

UVa logo 1158 - CubesSquared
UVa logo 10721 - Bar Codes
UVa logo 10081 - Tight words
OIE logo Parentizando
OIE logo Gramaticando