Aplicación de DP en tareas reales

7.1 Optimización de algoritmos dinámicos.

La optimización de algoritmos dinámicos se centra en mejorar su eficiencia temporal y espacial. Hay varias formas de optimización, incluyendo el uso de memoización, reducción de memoria utilizada y optimización de recursión.

1. Memoización:

La memoización es una técnica en la que se almacenan los resultados de los cálculos para evitar recalcular la misma sub-tarea.

Ejemplo:

En el problema de cambio de monedas, si usas un enfoque recursivo, puedes guardar los resultados para las sumas ya calculadas, evitando así recalcular.

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

2. Solución tabular (Bottom-Up):

La solución tabular (bottom-up) construye una tabla de soluciones para todas las posibles sub-tareas desde el caso base hasta la tarea objetivo. Esto permite evitar el coste de llamadas recursivas.

Ejemplo:

En el problema de la mochila, se construye una tabla de las cantidades mínimas de monedas para cada suma de 0 a S.

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

3. Reducción de memoria utilizada:

En algunos problemas, puedes optimizar el uso de la memoria reduciendo el tamaño de la tabla o el array utilizado para almacenar resultados intermedios.

Ejemplo:

En el problema de la mochila, se puede usar un array unidimensional en lugar de una tabla bidimensional si solo se almacenan la fila actual y la anterior.

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

4. Recursión de cola:

La recursión de cola es una llamada recursiva que se ejecuta al final de una función. Esto permite al compilador o intérprete optimizar el stack de llamadas.

Ejemplo:

En el problema de calcular los números de Fibonacci, se puede usar recursión de cola con un acumulador de resultados.

7.2 Aplicación del dynamic programming en tareas reales.

El dynamic programming encuentra una amplia aplicación en diversas áreas, incluyendo ciencias de la computación, economía, bioinformática e investigación operativa. Aquí hay algunos ejemplos de su uso en tareas reales:

1. Optimización de rutas y logística:

En problemas de logística y sistemas de transporte, se usa el dynamic programming para encontrar rutas óptimas y minimizar costes.

Ejemplo:

El problema del viajero de comercio (Travelling Salesman Problem, TSP) trata de encontrar el camino más corto que pase por todas las ciudades.

def tsp(graph, start):
    n = len(graph)
    dp = [[None] * (1 << n) for _ in range(n)]

    def visit(city, visited):
        if visited == (1 << n) - 1:
            return graph[city][start]
        if dp[city][visited] is not None:
            return dp[city][visited]
        result = float('inf')
        for next_city in range(n):
            if visited & (1 << next_city) == 0:
                result = min(result, graph[city][next_city] + visit(next_city, visited | (1 << next_city)))
        dp[city][visited] = result
        return result

    return visit(start, 1 << start)

2. Alineación de secuencias en bioinformática:

En bioinformática, el dynamic programming se usa para alinear secuencias de ADN, ARN y proteínas.

Ejemplo:

El algoritmo de Needleman-Wunsch para alineación global de secuencias y el algoritmo de Smith-Waterman para alineación local.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
        

3. Cálculos financieros y planificación económica:

El dynamic programming se aplica para optimizar carteras de inversión, gestión de riesgos y planificación de producción.

Ejemplo:

El problema del cambio de monedas y el problema de la mochila se utilizan para la gestión de activos y la asignación óptima de recursos.

4. Gestión de inventarios y producción:

En la producción y gestión de inventarios, el dynamic programming ayuda a optimizar procesos y minimizar costes.

Ejemplo:

Modelo de gestión de inventarios (Inventory Management Model) para minimizar los costes de almacenamiento y pedido de producción.

5. Aprendizaje automático y inteligencia artificial:

En el aprendizaje automático, el dynamic programming se usa para optimizar algoritmos y encontrar óptimos globales.

Ejemplo:

Algoritmos de aprendizaje basados en dynamic programming, como el método de retro-propagación en redes neuronales.