Saltar al contenido
Volver a los resultados

Programación Dinámica

Propuesto por
Richard Bellman
Año
1957
Tipo
Exact combinatorial optimization via recursive decomposition
Familia
Mathematical programming

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La Programación Dinámica (PD) es una técnica de optimización exacta introducida por Richard Bellman en 1957 para resolver problemas de decisión multietapa.

Descompone un problema complejo en subproblemas más simples y superpuestos, resuelve cada subproblema una vez y almacena los resultados para evitar cálculos redundantes. Basada en el Principio de Optimalidad, la PD garantiza soluciones globalmente óptimas siempre que el problema presente subproblemas superpuestos y subestructura óptima.

La intuición detrás del método

Imagine que planifica la ruta más corta a través de una ciudad encontrando primero las rutas más cortas entre cada par de intersecciones cercanas, y luego combinando esas pequeñas soluciones hacia arriba. En lugar de reexaminar todas las posibles rutas completas desde cero, reutiliza respuestas locales precalculadas. La Programación Dinámica funciona de la misma manera: almacena en caché las soluciones a subproblemas pequeños para que la construcción de la respuesta completa requiera solo búsquedas en tablas en lugar de cálculos intensivos repetidos.

Historia

Richard Bellman acuñó el término 'programación dinámica' en 1957 mientras trabajaba en RAND Corporation, eligiendo deliberadamente la palabra 'programación' para referirse a la planificación en lugar de la codificación informática. El Principio de Optimalidad que enunció se convirtió en la base teórica para la teoría de control, la investigación de operaciones y, más tarde, el aprendizaje por refuerzo. Los algoritmos clásicos de PD —el camino más corto de Dijkstra, el algoritmo de Viterbi y el alineador de secuencias de Needleman-Wunsch— derivan directamente del marco de Bellman.

Cuándo usarlo

La Programación Dinámica es apropiada cuando un problema tiene subproblemas superpuestos y subestructura óptima —propiedades comunes en la toma de decisiones secuencial, asignación de recursos, planificación y tareas de alineación de secuencias. Requiere que el espacio de estados sea completamente enumerable y de tamaño manejable; el método sufre la maldición de la dimensionalidad cuando las variables de estado son muchas o continuas. Para problemas con espacios de estados intratables, la PD aproximada o el aprendizaje por refuerzo son alternativas preferibles.

Limitaciones y consideraciones

  • Sufre la maldición de la dimensionalidad: los requisitos de memoria y tiempo crecen exponencialmente con el número de variables de estado.
  • Requiere conocimiento previo completo de la estructura de transición y la función de recompensa; inaplicable a entornos desconocidos sin aproximación.
  • El espacio de estados debe ser discreto o discretizable; los problemas continuos de alta dimensión exigen esquemas de aproximación que sacrifiquen la exactitud.
  • La formulación de la representación de estado y la relación de recurrencia correctas requiere una visión profunda específica del problema.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Garantiza soluciones óptimas globales exactas para problemas que satisfacen el Principio de Optimalidad.
  • Elimina cálculos redundantes mediante memorización, logrando tiempo polinomial en el número de estados.
  • Produce una política óptima explícita, no meramente un valor óptimo, permitiendo un soporte de decisiones directo.
  • Amplia aplicabilidad en dominios que incluyen teoría de control, bioinformática, economía e investigación de operaciones.

Aplicaciones

  • Problemas de camino más corto y enrutamiento en redes (Bellman-Ford, variantes de Dijkstra).
  • Alineación de secuencias en biología computacional (algoritmos de Needleman-Wunsch, Smith-Waterman).
  • Asignación óptima de recursos y problemas combinatorios tipo mochila en investigación de operaciones.
  • Reconocimiento de voz y escritura a mano a través del algoritmo de Viterbi en Modelos Ocultos de Markov.
  • Control óptimo y optimización de carteras multiperíodo en economía e ingeniería.

Cómo funciona

Cómo funciona

1

El problema general de optimización se expresa como una relación de recurrencia. Para cada estado s y etapa de decisión n, la función de valor V_n(s) es igual a la mejor recompensa inmediata más el valor descontado del siguiente estado resultante. Esta ecuación de Bellman formaliza el Principio de Optimalidad: cualquier sub-ruta de una ruta óptima debe ser en sí misma óptima.

Fórmula
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]
2

La recurrencia se resuelve de forma iterativa o recursiva. En la iteración de valor, V^*(s) se actualiza repetidamente en todos los estados hasta la convergencia, utilizando la estimación actual de los valores de los estados vecinos. Cada actualización reemplaza el valor antiguo con la mejor recompensa alcanzable más el valor futuro, propagando la información de optimalidad a través del espacio de estados.

Fórmula
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)
3

Los valores calculados se almacenan en una tabla indexada por estado. Los estados terminales reciben un valor base de cero (o una recompensa conocida), y todas las demás entradas se completan a medida que se resuelven los subproblemas. La memorización asegura que cada estado se evalúe como máximo una vez, reduciendo la búsqueda recursiva exponencial a tiempo polinomial en el número de estados y etapas.

Fórmula
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}
4

Una vez que la tabla de valores está completa, la política óptima pi^*(s) se recupera mediante un simple pase codicioso: para cada estado, se selecciona la acción que maximiza la recompensa inmediata más el valor almacenado del estado sucesor. Esta extracción en un solo pase es computacionalmente barata y produce una regla de decisión determinista y globalmente óptima.

Fórmula
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]

Errores comunes

  • Definir una representación de estado insuficientemente expresiva conduce a recurrencias incorrectas y soluciones subóptimas.
  • Confundir la memorización de arriba hacia abajo con la tabulación de abajo hacia arriba puede producir errores de desbordamiento de pila u orden incorrecto de la evaluación de subproblemas.
  • Aplicar PD a problemas que carecen de subestructura óptima (por ejemplo, el camino más largo en un grafo general) produce resultados incorrectos sin advertencia.
  • Ignorar la precisión numérica en los cálculos de recompensa acumulada puede causar errores sutiles de optimalidad en implementaciones de punto flotante.

Preguntas frecuentes

¿Cuál es la diferencia entre programación dinámica y divide y vencerás?

Ambos descomponen problemas en subproblemas, pero divide y vencerás asume subproblemas independientes que se resuelven una sola vez de forma natural. La programación dinámica se enfoca en subproblemas superpuestos —el mismo subproblema aparece en múltiples ramas— y memoriza los resultados para evitar trabajo redundante. Sin subproblemas superpuestos, la PD no ofrece ventaja computacional sobre la recursión directa.

¿Cuándo debo usar memorización de arriba hacia abajo en lugar de tabulación de abajo hacia arriba?

La memorización de arriba hacia abajo es más fácil de implementar directamente desde la recurrencia y calcula solo los subproblemas necesarios, lo que beneficia a los espacios de estados dispersos. La tabulación de abajo hacia arriba evita la sobrecarga de la recursión y los límites de la pila, se adapta a espacios de estados densos y a menudo es más rápida en la práctica. Elija de arriba hacia abajo cuando el conjunto de subproblemas necesarios sea difícil de predecir, de abajo hacia arriba cuando se necesiten todos los subproblemas.

¿Cómo se relaciona la programación dinámica con el aprendizaje por refuerzo?

La PD clásica requiere un modelo de Proceso de Decisión de Markov completamente conocido (probabilidades de transición y recompensas). El aprendizaje por refuerzo extiende las ideas de la PD a entornos donde el modelo es desconocido, utilizando experiencia muestreada en su lugar. Algoritmos como Q-learning y los métodos de gradiente de política son procedimientos de PD aproximada que aprenden funciones de valor a partir de la interacción en lugar de un modelo explícito.

Métodos relacionados

Fuentes

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.

    ISBN: 978-0-691-07951-6
    Copiado.