Fundamentos de la programación dinámica

5.1 Definición de programación dinámica.

Programación Dinámica (Dynamic Programming, DP) es un método de optimización que se usa para resolver problemas complejos dividiéndolos en subproblemas más simples. La programación dinámica se utiliza de manera efectiva para problemas que se pueden dividir en subproblemas superpuestos con una estructura óptima de subproblemas.

Principios de funcionamiento:

1. Subestructura óptima:

Un problema tiene una subestructura óptima si su solución óptima se puede construir a partir de soluciones óptimas de sus subproblemas. Esto significa que puedes resolver un problema grande resolviendo varios subproblemas más pequeños.

2. Subproblemas superpuestos:

Un problema tiene subproblemas superpuestos si sus subproblemas se repiten varias veces durante el proceso de resolución. La programación dinámica resuelve eficazmente problemas con subproblemas superpuestos mediante el almacenamiento de resultados de subproblemas ya resueltos (memoización).

3. Memoización y tabulación:

Memoización (de arriba hacia abajo): Enfoque recursivo donde los resultados de los subproblemas se guardan en memoria para evitar cálculos repetidos.

Tabulación (de abajo hacia arriba): Enfoque iterativo donde los resultados de los subproblemas se calculan y almacenan en una tabla (normalmente un array) y se utilizan para calcular el resultado final.

Ejemplos de problemas resueltos mediante programación dinámica

5.2 El problema de la mochila.

Problema:

Tienes un conjunto de objetos, cada uno con un peso y un valor. Debes elegir objetos para una mochila con una capacidad máxima, de modo que se maximice el valor total.

¡Importante! A diferencia de un problema similar, que se resolvía bien con un algoritmo voraz, en este problema no se pueden fraccionar los objetos.

Solución:

Se crea una tabla en la que las filas corresponden a los objetos y las columnas a las capacidades posibles de la mochila. El valor en la celda representa el valor máximo para ese número de objetos y capacidad.

Complejidad temporal: O(n * W), donde n es la cantidad de objetos, W es la capacidad de la mochila.

Ejemplo de código en Python:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 El problema de encontrar el camino más corto

Problema:

Encontrar los caminos más cortos entre todos los pares de nodos en un grafo ponderado.

Solución:

Se utiliza una tabla donde las filas y columnas corresponden a los nodos del grafo. El valor en la celda representa la distancia más corta entre dos nodos.

Complejidad temporal: O(V^3), donde V es la cantidad de nodos

Ejemplo de código en Python:

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 Comparación de la programación dinámica con otros métodos.

Comparación con el método de fuerza bruta (brute force):

Complejidad temporal:

• Fuerza bruta: a menudo tiene una complejidad temporal exponencial (por ejemplo, O(2^n) para el problema de Fibonacci).
• Programación dinámica: reduce la complejidad temporal a polinómica (por ejemplo, O(n) para el problema de Fibonacci).

Complejidad espacial:

• Fuerza bruta: puede usar menos memoria, pero los costos temporales son altos.
• Programación dinámica: puede usar más memoria para almacenar resultados intermedios (por ejemplo, O(n) para el problema de Fibonacci con memoización), pero ahorra tiempo.

Comparación con el método de algoritmos voraces (greedy algorithms):

Optimalidad:

• Algoritmos voraces: no siempre encuentran la solución globalmente óptima, pero funcionan más rápido y son más fáciles de implementar.
• Programación dinámica: encuentra una solución globalmente óptima, pero requiere más recursos computacionales.

Ejemplos de problemas:

• Algoritmos voraces: problema de la mochila con fracciones (fractional knapsack), árbol de expansión mínima (MST).
• Programación dinámica: problema de la mochila (entera), subsecuencia común más larga (LCS).