Programación dinámica (DP) es una técnica de optimización.
Descompone un problema complejo en subproblemas más pequeños
Almacena sus soluciones para evitar cálculos repetitivos.
Se usa ampliamente en aprendizaje por refuerzo
Algoritmos de búsqueda y optimización en IA.
Principio clave:
«Resolver un problema grande resolviendo y combinando soluciones
de problemas más pequeños ya resueltos.»
Características clave de la Programación Dinámica
Superposición de subproblemas
Se resuelven los mismos subproblemas múltiples veces.
Optimalidad de subestructura
La solución óptima global depende.
De soluciones óptimas de subproblemas.
Uso de memoria (memoización o tabulación)
Se almacenan soluciones previas para mejorar eficiencia.
Aplicaciones de la Programación Dinámica en IA
Aprendizaje por Refuerzo (Reinforcement Learning – RL)
En algoritmos como Q-Learning, se utiliza DP.
Encontrar la política óptima.
De un agente en un entorno.
Métodos como Value Iteration y Policy Iteration
Dependen de DP para calcular la función.
De valor óptima.
Ejemplo
Algoritmo de Iteración de Valores
Optimización de Algoritmos de Búsqueda
Se usa en algoritmos como A y búsqueda heurística*
Encontrar caminos óptimos.
Ejemplo
Optimización en procesamiento de lenguaje natural (NLP)
Visión por computadora para reducir cálculos redundantes.
Series Temporales y Predicciones
En modelos de predicción como Hidden Markov Models (HMMs)
Redes Neuronales Recurrentes (RNNs)
Ejemplo
Algoritmo de Viterbi en reconocimiento de voz.
Procesamiento de texto.
Métodos de Programación Dinámica
Memoización (Top-Down)
Se usa recursión y almacenamiento en caché.
Evitar cálculos repetidos.
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]
print(fibonacci(10)) # Output: 55
Ventaja
Evita cálculos redundantes al almacenar resultados previos.
Tabulación (Bottom-Up)
Se resuelven primero los subproblemas más pequeños.
Se almacenan en una tabla.
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]
print(fibonacci(10)) # Output: 55
Ventaja
Evita la sobrecarga de llamadas recursivas y es más eficiente en memoria.
La programación dinámica es para resolver problemas de optimización.
Planificación y aprendizaje por refuerzo.
Clave
Descomponer problemas en partes más pequeñas y reutilizar soluciones previas.
Se usa en:
Búsqueda de caminos, NLP, visión por computadora, aprendizaje por refuerzo y más.
