Introducción

Frecuentemente para resolver un problema complejo se tiende a dividir este en subproblemas más pequeños, resolver estos últimos (recurriendo posiblemente a nuevas subdivisiones) y combinar las soluciones obtenidas para calcular la solución del problema inicial (esa es la manera de trabajar, por ejemplo, del método divide y vencerás). Puede ocurrir que la división natural del problema conduzca a un gran número de subproblemas idénticos. Si se resuelve cada uno de ellos sin tener en cuenta las posibles repeticiones, resulta un algoritmo ineficiente; en cambio si se resuelve cada ejemplar distinto una sola vez y se conserva el resultado, el algoritmo obtenido es mucho mejor.

Esta es la idea de la programación dinámica: no calcular dos veces lo mismo y utilizar normalmente una tabla de resultados que se va rellenando a medida que se resuelven los subproblemas.

Ideas generales

La programación dinámica es una técnica que se suele utilizar para resolver problemas de optimización, donde una solución está formada por una serie de decisiones. En esto coincide con el método voraz o de avance rápido, pero, a diferencia de este, en la programación dinámica se obtiene la solución óptima, y no una aproximación de ella. La programación dinámica es una técnica ascendente, en la que se parte de la solución de los problemas de menor tamaño para obtener la del tamaño mayor, que se pretende resolver.

Igual que la técnica divide y vencerás, resuelve el problema original combinando las soluciones para subproblemas más pequeños. Sin embargo, la programación dinámica no utiliza recursividad, sino que almacena los resultados de los subproblemas en una tabla, calculando primero las soluciones para problemas más pequeños. Con esto se pretende evitar la repetición de cálculos que se puede dar cuando se resuelve un problema con llamadas recursivas a problemas más pequeños, con lo que se repiten llamadas a problemas idénticos, lo que supone la repetición de cálculos innecesariamente, pues se podrían haber guardado las soluciones obtenidas anteriormente.

Ejemplo 1: Los números de Fibonacci están definidos por la recurrencia:

F(n) = F(n - 1) + F(n - 2), con casos base F(1) = F(2) = 1.

Para calcular un número de Fibonacci se puede usar un método recursivo:

operación Fibonacci (n: entero): entero

    si n ≤ 2 entonces devolver 1

    si no devolver Fibonacci (n -1) + Fibonacci (n - 2)

finsi

Esta solución se puede ver como un esquema divide y vencerás, pues para resolver un problema de tamaño n resolvemos dos problemas de tamaño menor, y combinamos los resultados sumándolos. De esta forma se repiten muchos cálculos. Por ejemplo, para calcular F(5) tenemos F(5) = F(4) + F(3) = F(3) + F(2) + F(3), con lo que vemos que F(3) se calcula dos veces. Esta repetición de cálculos produce un tiempo exponencial, como podemos ver resolviendo la recurrencia t(n) = t(n - 1) + t(n - 2) + 1, que da como resultado t(n) Î Θ (((1+Ö5)/2)ⁿ).

Ejemplo 2: Un fenómeno similar ocurre con el cálculo de números combinatorios. El algoritmo sería:

operación C(n, k)

    si k=0 o k=n entonces devolver 1

    si no devolver C(n-1, k-1) + C(n-1, k)

    finsi

Ocurre que muchos valores C(i, j), con i<n y j<k se calculan y recalculan varias veces.

Principio fundamental

Con la programación dinámica se evitan cálculos repetidos guardando una tabla de resultados de subproblemas, es por tanto un método ascendente, donde partimos de problemas de tamaño mínimo y vamos obteniendo resultados de problemas de tamaño cada vez mayor hasta llegar al tamaño del problema a resolver. Se diferencia de la técnica divide y vencerás en que este método es descendente, pues se empieza con el problema original y se descompone en sucesivos pasos en problemas de menor tamaño.

Para poder aplicar la técnica de programación dinámica a un problema de optimización se debe cumplir el principio de optimalidad de Bellman, que dice que en una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima. Por tanto, el primer paso para aplicar programación dinámica a la solución de un problema es comprobar si se cumple el principio de optimalidad. Algunas veces se cumple dependiendo de la forma en que se enfoque el problema, como vemos en el ejemplo siguiente.

Ejemplo 3: Consideramos el grafo multietapa de la siguiente figura.

El camino de longitud mínima del nodo 1 al 9 está formado por las aristas (1,3), (3,5), (5,7) y (7,9). Si consideramos como subproblemas la obtención del camino de longitud mínima del nodo 1 a los sucesivos niveles del grafo, el principio de optimalidad no se cumple, pues al segundo nivel el camino mínimo se obtiene con la arista (1,4), que no forma parte de la secuencia solución del problema total. Tampoco se puede obtener la secuencia óptima como concatenación de secuencias óptimas de subproblemas, pues para pasar del nivel uno al dos, la arista óptima es (1,4), para pasar del dos al tres es la (3,5), etc., y concatenando las aristas ni siquiera tenemos un camino del nodo 1 al 9. Esto no quiere decir que el problema no cumpla el principio de optimalidad, sino que no lo cumple tal como lo hemos enfocado. Si consideramos como subproblema la obtención del camino mínimo del nodo origen a cada uno de los restantes nodos, la arista (1,3) es obviamente la solución óptima para llegar del nodo 1 al 3, la sucesión (1,3), (3,5) es óptima para llegar del 1 al 5, y la sucesión (1,3), (3,5), (5,7) lo es para llegar del 1 al 7.

Pasos en la resolución

Los pasos a seguir para obtener un algoritmo de programación dinámica son:

·        Verificar que la solución puede alcanzarse a partir de una sucesión de decisiones y que esta cumple el principio de optimalidad.

·        Encontrar la ecuación recurrente que liga la solución de problemas de un tamaño con soluciones de problemas de tamaños menores.

·        Establecer los casos base y su valor.

·        Definir las tablas a utilizar por el algoritmo, y determinar la forma en que se rellenan.

·        Expresar cómo se recompone la solución global a partir de los valores de las tablas.

Ejemplo 4: En el cálculo de los números de Fibonacci la ecuación de recurrencia es la que los define:

Para este problema es posible diseñar un algoritmo que en tiempo lineal lo resuelva mediante la construcción de una tabla que permita ir almacenando los cálculos realizados hasta el momento para poder reutilizarlos:

La tabla que se utiliza es el array de 1 a n donde se almacenan los números. En este caso no hay que recomponer la solución, pues no se obtiene como una secuencia de decisiones, y lo único que importa es el valor del número de Fibonacci.

operación Fibonacci (n: entero): entero

    si n < 0 devolver error

    si no

        f[0]:=1

        f[1]:=1

        para i=2,...,n hacer

            f[i]:=f[i-1]+f[i-2]

        finpara

    finsi

    devolver f[n]

De esta forma el tiempo de ejecución es Θ (n).

El uso de estructuras (vectores o tablas) para eliminar la repetición de los cálculos, pieza clave de los algoritmos de programación dinámica, hace que nos fijemos no sólo en la complejidad temporal de los algoritmos estudiados, sino también en su complejidad espacial.

En general, los algoritmos obtenidos mediante la aplicación de esta técnica consiguen tener complejidades (espacio y tiempo) bastante razonables, pero debemos evitar que el tratar de obtener una complejidad temporal de orden polinómico conduzca a una complejidad espacial demasiado elevada, como veremos en alguno de los ejemplos de este capítulo.

Ejemplo 5: En el caso del cálculo de números combinatorios, la recurrencia tendría la siguiente forma:

 =  +      si 0 < k < n,     =  = 1

El algoritmo recursivo que calcula los valores resulta ser de complejidad exponencial por la repetición de los cálculos que realiza. No obstante, es posible diseñar un algoritmo con un tiempo de ejecución de orden O(nk) basado en la idea del Triángulo de Pascal. Para ello es necesario la creación de una tabla bidimensional en la que ir almacenando los valores intermedios que se utilizan posteriormente:

Iremos construyendo esta tabla por filas de arriba hacia abajo y de izquierda a derecha mediante el siguiente algoritmo de complejidad polinómica:

operación C(n, k)

    para i=0...n hacer

        C[i,0] = 1

    finpara

    para i=1...n hacer

        C[i,1] = i

    finpara

    para i=2...k hacer

        C[i,i] = 1

    finpara

    para i=3...n hacer

        para i=2...i-1 hacer

            si j ≤ k

                C[i,j] = C[i-1, j-1] + C[i-1, j]

            fin si

        finpara

    finpara

Tiempo de ejecución y memoria

En general el estudio del tiempo de ejecución y ocupación de memoria es muy simple para esta técnica, al tratarse de rellenar una tabla de soluciones. El tiempo de ejecución depende del tipo de problema a resolver, pero en general será de la forma: (Tamaño de la tabla) * (Tiempo de rellenar cada elemento de la tabla).

Otro aspecto importante de los algoritmos de programación dinámica es la alta ocupación de memoria, al necesitarse una tabla para almacenar los resultados parciales.

Muchos de los cálculos y de la ocupación de memoria pueden ser innecesarios, pues los subproblemas a que corresponden no aparecerán en la solución final, pero puede ser preferible esto a la repetición de cálculos que se daría si el problema se resolviera de manera recursiva.

Problema de la mochila

Tanto en el ejemplo de la obtención de los números de Fibonacci como en el del cálculo de un número combinatoria, la solución la obtenemos directamente de la última posición de la tabla y no ha habido que reconstruirla. Vamos a ver un problema en el que sí es necesario ese proceso.

Consideremos el problema de la mochila 0/1: mochila de capacidad M, y n objetos de beneficios b = (b₁, b₂,... b_n) y pesos p = (p₁, p₂,... p_n); en el problema de la mochila 0/1 no se pueden introducir en la mochila porciones de elementos, con lo que cada x_i es 0 o 1 dependiendo de que no se introduzca o sí se introduzca el elemento en la mochila. El problema consiste en maximizar b_ix_i  sujeto a p_ix_i ≤ M, donde x_i=0 o x_i=1 "i, con 1 ≤ i ≤ M.