¿Qué es la programación dinámica?

La programación dinámica, cuando se refiere al campo de la informática, describe un grupo de algoritmos informáticos similares destinados a resolver problemas complejos dividiendo el problema en conjuntos de problemas más pequeños. Creado por primera vez por Richard Bellman en la década de 1950, la programación dinámica funciona con problemas que se superponen a subproblemas o subestructuras óptimas. Para comprender cómo funciona la programación dinámica, es mejor comprender el concepto detrás de estos dos términos.

Los subproblemas superpuestos describen ecuaciones complicadas que, cuando se dividen en conjuntos de ecuaciones más pequeños, reutilizan partes de las ecuaciones más pequeñas más de una vez para llegar a una respuesta. Por ejemplo, una ecuación matemática a la que se le dice que calcule todos los resultados posibles usando un conjunto de números puede calcular el mismo resultado varias veces mientras calcula otros resultados solo una vez. La programación dinámica le dirá a este problema que después de calcular el resultado la primera vez, debe guardar ese resultado y conectar la respuesta a la ecuación más adelante en lugar de calcularlo nuevamente. Cuando se trata de ecuaciones y procesos complejos largos, esto ahorra tiempo y crea una solución más rápida con muchos menos pasos.

Las subestructuras óptimas crean una solución al encontrar la mejor respuesta a todos los subproblemas y luego crean la mejor respuesta general. Después de dividir un problema complejo en problemas más pequeños, la computadora usa un sistema matemático para determinar cuál es la mejor respuesta para cada problema. Calcula la respuesta al problema original a partir de las respuestas más pequeñas. Existen fallas con este proceso. Si bien ofrece la solución que funciona mejor matemáticamente, puede ser o no la mejor solución en la vida real, dependiendo del tipo de problema y de cómo se relaciona con el mundo real.

Durante cualquiera de estas operaciones, el algoritmo de programación dinámica intenta encontrar el camino más corto hacia la solución. Puede tomar uno de dos enfoques para hacer esto. El enfoque de arriba hacia abajo divide la ecuación en ecuaciones más pequeñas y reutiliza las respuestas para estas ecuaciones cuando es necesario. El enfoque de abajo hacia arriba intenta resolver el valor matemático más pequeño después de desglosar la ecuación y luego avanza hacia el más grande desde allí. Ambos enfoques ahorran tiempo, pero la programación dinámica solo funciona cuando el problema original puede descomponerse en ecuaciones más pequeñas que en algún momento se reutilizan para resolver la ecuación.