Esto es un poco confuso porque hay dos cosas diferentes que comúnmente se conocen con el nombre de “programación dinámica”: un principio de diseño de algoritmos y un método para formular un problema de optimización. Me voy a concentrar en comparar los dos métodos de optimización.
Un programa lineal es un problema de optimización en el que queremos minimizar una función lineal sujeta a algunas restricciones lineales. Vea el primer ejemplo en Wikipedia para un problema de programación lineal muy simple.
En un programa dinámico, queremos tomar una serie de decisiones de tal manera que se maximice alguna función. La clave es que el conjunto de decisiones disponibles para nosotros en cualquier momento depende de lo que ya hayamos decidido hacer anteriormente. El ejemplo más simple que conozco es el problema óptimo de consumo y ahorro descrito en Wikipedia.
- ¿Cuál es una forma rápida de factorizar números con 12 dígitos sin utilizar ningún algoritmo de división de prueba o Pollard-Rho?
- ¿Cuáles son los ejemplos de colas en la vida real con algoritmo?
- ¿Has visto algún trabajo hacia el cierre transitivo de la alineación de secuencias y las matrices de sustitución?
- ¿Los investigadores que elaboran algoritmos útiles ganan mucho dinero cuando sus algoritmos se aplican ampliamente en la industria?
- Actualmente estoy leyendo un libro sobre estructuras de datos y algoritmos. ¿Cuáles son algunos recursos que puedo usar para practicar la implementación?
La diferencia clave entre los dos es que en la programación dinámica estamos tomando una decisión a la vez, mientras que en la programación lineal estamos tomando todas las decisiones por adelantado.
