Programación Dinámica

La programación dinámica es un paradigma de diseño de algoritmos que resuelve problemas con subestructura óptima y subproblemas superpuestos, resolviendo cada subproblema una vez y almacenando su resultado para su reutilización, transformando la recálculo exponencial en un cálculo de tiempo polinómico.

Definition

La programación dinámica es un método que resuelve un problema de optimización o conteo definiendo su valor recursivamente en términos de subproblemas superpuestos y calculando cada subproblema distinto exactamente una vez, almacenando en caché el resultado para que pueda ser reutilizado en lugar de recalculado.

Scope

Este tema cubre las dos características distintivas que hacen aplicable la programación dinámica —subestructura óptima y subproblemas superpuestos— y los dos estilos de implementación, memoización de arriba hacia abajo y tabulación de abajo hacia arriba. Incluye problemas canónicos como la subsecuencia común más larga, la distancia de edición, la mochila, la multiplicación de cadenas de matrices y los programas dinámicos de ruta más corta, junto con el diseño del espacio de estados y el análisis de las compensaciones de tiempo y espacio. Excluye los métodos de ruta más corta específicos de grafos tratados en algoritmos de grafos, aunque comparten el mismo principio subyacente.

Core questions

• ¿El problema tiene una subestructura óptima que permite construir una solución óptima a partir de subsoluciones óptimas?
• ¿Cómo se define el conjunto de subproblemas (el espacio de estados) para que cada uno recurra solo un número polinómico de veces?
• ¿Debe implementarse la solución de arriba hacia abajo con memoización o de abajo hacia arriba con tabulación?
• ¿Cómo se puede reconstruir la tabla para recuperar la solución óptima real, no solo su valor?
• ¿Cómo se puede reducir el espacio cuando solo se necesita una parte de la tabla en cada paso?

Key concepts

• subestructura óptima
• subproblemas superpuestos
• principio de optimalidad
• memoización
• tabulación
• espacio de estados y recurrencia
• subsecuencia común más larga
• distancia de edición
• problema de la mochila

Key theories

Principio de optimalidad

El principio de optimalidad de Bellman establece que una política óptima tiene la propiedad de que, cualesquiera que sean el estado inicial y la decisión, las decisiones restantes deben constituir una política óptima para el estado resultante, la base formal de las recurrencias de programación dinámica.

Memoización versus tabulación

Un programa dinámico puede realizarse de arriba hacia abajo añadiendo una caché a una formulación recursiva (memoización) o de abajo hacia arriba rellenando una tabla en orden de dependencia (tabulación); ambos calculan cada subproblema una vez, pero difieren en el orden de evaluación y el comportamiento del espacio.

Clinical relevance

La programación dinámica es omnipresente en la práctica: alineación de secuencias (Needleman-Wunsch, Smith-Waterman) en biología computacional, distancia de edición en la corrección ortográfica y diferencias de control de versiones, el algoritmo de Viterbi en el reconocimiento de voz y las comunicaciones, y programas dinámicos en investigación de operaciones, finanzas y aprendizaje por refuerzo.

History

Richard Bellman desarrolló la programación dinámica en la década de 1950 mientras trabajaba en la RAND Corporation, eligiendo el nombre en parte para que fuera aceptable para los patrocinadores de la investigación. El principio de optimalidad y la ecuación de Bellman se convirtieron en fundamentales en la investigación de operaciones, la teoría de control y la informática, y la técnica fue codificada posteriormente como un paradigma algorítmico central en los libros de texto de algoritmos.

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

¿Cuál es la diferencia entre dividir y conquistar y la programación dinámica?

Ambos descomponen un problema en subproblemas, pero los subproblemas de dividir y conquistar son independientes y se resuelven una vez, mientras que los subproblemas de programación dinámica se superponen y se recalcularían muchas veces mediante una recursión ingenua. La programación dinámica almacena en caché las soluciones de los subproblemas para evitar ese recálculo.

¿Cuándo no se aplica la programación dinámica?

Requiere una subestructura óptima y un conjunto de subproblemas distintos de tamaño polinómico. Si el problema carece de subestructura óptima, o si el espacio de estados natural es exponencial y no se puede comprimir, la programación dinámica es incorrecta o ya no es eficiente.