¿Qué es la programación dinámica?
Programación dinámica, al referirse al campo de la informática, describe un grupo de algoritmos informáticos similares destinados a resolver problemas complejos al dividir 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 descomponen en conjuntos más pequeños de ecuaciones, reutilizan partes de las ecuaciones más pequeñas más de una vez para alcanzar una respuesta. Por ejemplo, una ecuación matemática se le dice que calcule todos los resultados posibles utilizando un conjunto de números puede calcular el mismo resultado numerosas veces al calcular otros resultados solo una vez. La programación dinámica le diría a este problema que después de calcular el resultado la primera vez que debe guardar ese resultado y conectar la respuesta alecuación más adelante en lugar de calcularla nuevamente. Al tratar con procesos y ecuaciones complejas largos, esto ahorra tiempo y crea una solución más rápida utilizando muchos menos pasos.
Las subestructuras óptimas crean una solución al encontrar la mejor respuesta a todos los subproblemas y luego crear la mejor respuesta general. Después de romper 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 de las respuestas más pequeñas. Los defectos existen 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 cómo se relaciona con el mundo real.
Durante cualquiera de estas operaciones, el algoritmo de programación dinámica intenta encontrar la ruta más corta a la solución. Puede tomar uno deDos 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 sea necesario. El enfoque ascendente intenta resolver el valor matemático más pequeño después de romper la ecuación y luego avanzar hacia el más grande desde allí. Ambos enfoques ahorran tiempo, pero la programación dinámica solo funciona cuando el problema original puede dividirse en ecuaciones más pequeñas que en algún momento se reutilizan para resolver la ecuación.