4.3 Algoritmos de Programación Dinámica

La Programación Dinámica (PD) es una técnica algorítmica que descompone un problema de optimización en subproblemas más simples. La solución al problema general depende de la solución óptima de sus subproblemas.

La ventaja de la PD sobre los algoritmos de divide y vencerás es que la PD es aplicable a subproblemas dependientes. En otras palabras, cuando los subproblemas comparten sub-subproblemas, la PD funcionará mientras que los algoritmos de divide y vencerás no lo harán.

Los algoritmos de PD resuelven los subproblemas solo una vez y luego guardan la respuesta en una tabla. Esto evita la necesidad de volver a calcular la respuesta cada vez que se encuentra el subproblema. Esto ahorra tiempo y libera poder de cómputo para resolver otros problemas.

La PD es una técnica poderosa que tiene muchas aplicaciones en áreas como la informática, la economía y la ingeniería. Al descomponer problemas complejos en subproblemas más pequeños y manejables, la PD nos permite resolver problemas que de otro modo serían demasiado difíciles de abordar.

Considera el problema de calcular la secuencia de Fibonacci. Una solución recursiva ingenua sería la siguiente:

def fibonacci(n):
    if n <= 1:
       return n
    else:
       return (fibonacci(n-1) + fibonacci(n-2))

Este algoritmo funciona, pero es ineficiente. Realiza una cantidad excesiva de cálculos repetidos. Si dibujamos el árbol de recursión, descubriremos que calculamos los mismos subproblemas múltiples veces. Aquí es donde entra en juego la programación dinámica.

Podemos resolver este problema utilizando programación dinámica de dos formas: arriba hacía abajo (o memorización) y abajo hacía arriba.

Arriba hacía abajo (Memorización): En informática, el enfoque de arriba hacía abajo se usa a menudo para resolver problemas complejos. Implica descomponer un problema grande en subproblemas más pequeños, que luego se resuelven uno por uno.

Este método es especialmente útil cuando se resuelven problemas que tienen subproblemas superpuestos. Para evitar cálculos redundantes, se utiliza la técnica de memorización. La memorización es una forma de almacenamiento en caché donde se guardan los resultados de llamadas costosas a funciones y se devuelven cuando ocurren las mismas entradas nuevamente. Al hacerlo, el algoritmo puede evitar volver a calcular el mismo subproblema varias veces y mejorar su eficiencia general.

Así es como podríamos implementar la secuencia de Fibonacci con programación dinámica de arriba hacía abajo:

def fibonacci(n, memo = {}):
    if n <= 1:
       return n
    elif n not in memo:
       memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

Abajo hacía arriba: Este enfoque es lo opuesto. Comenzamos con el subproblema más simple y resolvemos iterativamente subproblemas más grandes. El enfoque de abajo hacia arriba es un método en el que comenzamos descomponiendo un problema en sus subproblemas más simples y luego, a través de un proceso iterativo, resolvemos subproblemas progresivamente más grandes. Este enfoque se usa a menudo en programación dinámica, donde la solución a un problema se basa en soluciones a subproblemas anteriores.

Al comenzar con subproblemas más pequeños, podemos avanzar gradualmente hasta resolver el problema en su conjunto, lo que permite una solución más eficiente y efectiva. A diferencia del enfoque de arriba hacia abajo, que implica descomponer un problema desde el nivel superior y trabajar hacia abajo hacia los subproblemas, el enfoque de abajo hacia arriba permite un proceso de solución más sistemático y organizado que asegura que ningún subproblema sea pasado por alto.

Aquí está la secuencia de Fibonacci nuevamente, esta vez con programación dinámica de abajo hacia arriba:

def fibonacci(n):
    fib = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

Ambos enfoques nos dan la misma respuesta, pero llegan allí de diferentes maneras. El enfoque de arriba hacia abajo generalmente es más fácil de entender porque está más cerca del enunciado original del problema. El enfoque de abajo hacia arriba suele ser más eficiente porque elimina los costos adicionales de la recursión.

La Programación Dinámica es una técnica poderosa que nos permite resolver muchos tipos de problemas en tiempo O(n^2), O(n^3) o incluso en tiempo lineal, lo que sería imposible de otra manera. Ejemplos de tales problemas son el problema de la mochila, el Problema del Viajante de Comercio, la Multiplicación en Cadena de Matrices, etc.

Una cosa importante a recordar: la programación dinámica solo funciona cuando cada subproblema es discreto, es decir, cuando no depende de otros subproblemas, por lo que no se puede usar para resolver problemas donde hay un estado en curso que afecta la solución.

Como nota adicional sobre la programación dinámica, vale la pena mencionar que el proceso de diseño de algoritmos de programación dinámica se puede dividir en una serie de pasos:

Caracterizar la estructura de una solución óptima.
Definir el valor de una solución óptima de forma recursiva en términos de subproblemas más pequeños.
Calcular el valor de una solución óptima (típicamente de abajo hacia arriba).
Construir una solución óptima para el problema a partir de la información calculada.

También vale la pena señalar que la programación dinámica se usa principalmente cuando la solución se puede expresar de manera recurrente en términos de resultados anteriores. Esto lo convierte en un método valioso en casos donde el número de subproblemas superpuestos en un enfoque de fuerza bruta explota exponencialmente.

Sin embargo, la programación dinámica no siempre es el método más eficiente o práctico para cada problema. Se utiliza mejor cuando se tiene un problema que se puede dividir en subproblemas más pequeños y esos subproblemas se 'reutilizan' varias veces.

En la próxima sección, nos sumergiremos en los Algoritmos Recursivos, que es otra categoría común y fundamental de algoritmos utilizados en la informática. A medida que avancemos en este libro, adquirirás una sólida comprensión de diferentes tipos de algoritmos y ganarás la habilidad de determinar qué tipo o tipos son más apropiados para cualquier problema dado. Esta es una habilidad clave en la informática y la ingeniería de software, y te será útil en cualquier campo o emprendimiento relacionado. ¡Así que continuemos nuestro viaje en el mundo de los algoritmos!