El término Programación Dinámica fue utilizado originalmente en los 1940’s por Richard Bellman para describir el proceso de resolver problemas donde se necesita encontrar las mejores decisiones una tras otra. Para 1953, el refinó esto a su significado moderno, el cual se refiere específicamente a anidar pequeños problemas de decisión dentro de grandes decisiones, luego de esto el campo fue reconocido por la lEEE como un tópico de análisis de sistemas e ingeniería.
¿Qué es programación dinámica?
Es un modelo de algoritmo que resuelve un problema complejo dividiéndolo en subproblemas, almacenando los resultados de los mismos para así evitar tener que volver a calcular esos resultados.
Esta programación se utiliza cuando se tienen problemas que se pueden dividir en subproblemas similares, de modo que sus resultados puedan ser reutilizados. En su gran mayoría, esta programación se utiliza para la optimización.
Las siguientes características esenciales son las que debe tener un problema para que se pueda aplicar la programación dinámica:
-Subestructura óptima
Esta característica expresa que un problema de optimización se puede resolver al combinar las soluciones óptimas de los problemas secundarios que lo conforman.
-Subproblemas sobrepuestos
El espacio de los subproblemas debe ser pequeño. Es decir, cualquier algoritmo recursivo que resuelva un problema deberá resolver los mismos subproblemas una y otra vez, en lugar de generar nuevos subproblemas.
-Enfoque de arriba hacia abajo
Si la solución a cualquier problema se puede formular recursivamente usando para ello la solución de sus subproblemas, y si estos subproblemas se superponen, entonces las soluciones a los subproblemas se podrán memorizar o almacenar fácilmente en una tabla.
-Enfoque ascendente
Luego que se formula de forma recursiva la solución de un problema en términos de sus subproblemas, se podrá intentar reformular el problema de manera ascendente: primero se intentarán resolver los subproblemas y usar sus soluciones para llegar a soluciones a los subproblemas más grandes.
Ventajas
Una de las principales ventajas de usar programación dinámica es que acelera el procesamiento, ya que se usan referencias que fueron previamente calculadas. Como es una técnica de programación recursiva, reduce las líneas de código del programa.
Desventajas
Se necesita mucha memoria para almacenar el resultado calculado de cada subproblema, sin poder garantizar que el valor almacenado se utilizará o no.
Aplicaciones
La programación dinámica es un método eficaz para resolver problemas que de otro modo podrían parecer extremadamente difíciles de resolver en un tiempo razonable.
Los algoritmos basados en el paradigma de programación dinámica se utilizan en muchas áreas de las ciencias, incluyendo muchos ejemplos en inteligencia artificial, desde la resolución de problemas de planificación hasta el reconocimiento de voz.
Recursividad vs programación dinámica
Si se tiene memoria limitada para ejecutar el código y no es preocupante la velocidad de procesamiento, se puede usar la recursividad. Por ejemplo, si se está desarrollando una aplicación móvil, la memoria es muy limitada para ejecutar la aplicación.
Si se desea que el programa se ejecute más rápido y no se tienen restricciones de memoria, es preferible utilizar la programación dinámica.
Referencias
Corvo, H. S. (2020, 14 marzo). Programación dinámica: características, ejemplo, ventajas, desventajas. Lifeder. https://www.lifeder.com/programacion-dinamica/
4.12. Programación dinámica — Solución de problemas con algoritmos y estructuras de datos. (s. f.). runestone.academy. https://runestone.academy/runestone/static/pythoned/Recursion/ProgramacionDinamica.html
EcuRed. (s. f.). Programación dinámica - EcuRed. https://www.ecured.cu/Programaci%C3%B3n_din%C3%A1mica