Publicado · en mejora
Algorithm
La programación dinámica reutiliza las soluciones de subproblemas superpuestos y convierte búsquedas exponenciales en algoritmos eficientes basados en tablas.
La programación dinámica (DP) es una técnica de diseño de algoritmos que divide un problema en subproblemas más pequeños, resuelve cada uno una sola vez, guarda la respuesta y la reutiliza cada vez que el mismo subproblema vuelve a aparecer. Richard Bellman la formalizó en los años cincuenta. Se aplica cuando los subproblemas se superponen y cuando la solución óptima puede construirse a partir de las soluciones óptimas de sus subproblemas.
Muchos problemas que con recursión simple o fuerza bruta tardan un tiempo exponencial pasan a resolverse en un tiempo proporcional al número de estados. La programación dinámica está detrás de las herramientas diff, de la distancia de edición en los correctores ortográficos, del alineamiento de secuencias de ADN, del algoritmo de Viterbi en el reconocimiento de voz y del orden de los joins en los optimizadores de bases de datos. Además, es uno de los temas más habituales en las entrevistas técnicas.
Para empezar, usa Fibonacci para entender la diferencia entre memoización (de arriba abajo) y tabulación (de abajo arriba), y luego resuelve los clásicos: cambio de monedas, mochila 0/1, subsecuencia creciente más larga, subsecuencia común más larga y distancia de edición. En cada problema, define primero el estado, la recurrencia, los casos base y el orden de cálculo, comprueba la recurrencia rellenando una tabla pequeña a mano y solo después escribe el código.
Cuando el mismo subproblema aparece muchas veces, se calcula una sola vez y se guarda, de modo que el trabajo repetido se convierte en una consulta a la tabla.
La solución óptima debe poder construirse con soluciones óptimas de los subproblemas; esta propiedad justifica la recurrencia.
Se implementa de arriba abajo añadiendo una caché a la recursión (functools.cache) o de abajo arriba rellenando una tabla con bucles.
El estado incluye solo los parámetros que determinan la respuesta, y con arreglos rodantes se conservan únicamente las filas necesarias.
knapsack resuelve el problema de la mochila 0/1 de abajo arriba con una sola fila y recorre las capacidades de mayor a menor para que cada objeto se use como máximo una vez. lcs calcula la longitud de la subsecuencia común más larga de arriba abajo, con memoización mediante functools.cache. Al ejecutar python dynamic_programming.py se imprimen 9 y 4.
dynamic_programming.py
from functools import cache
def knapsack(weights, values, capacity):
"""0/1 knapsack: best total value within capacity (bottom-up, one row)."""
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
for c in range(capacity, w - 1, -1): # high to low: each item used at most once
best[c] = max(best[c], best[c - w] + v)
return best[capacity]
def lcs(a, b):
"""Length of the longest common subsequence (top-down, memoized)."""
@cache
def solve(i, j):
if i == len(a) or j == len(b):
return 0
if a[i] == b[j]:
return 1 + solve(i + 1, j + 1)
return max(solve(i + 1, j), solve(i, j + 1))
return solve(0, 0)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9
print(lcs("ABCBDAB", "BDCABA")) # 4
python dynamic_programming.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Programación dinámica.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Programación dinámica.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.