En matemáticas y ciencias de la computación , la programación dinámica es un método para resolver problemas complejos por su desglose en subproblemas más simples. Es aplicable a los problemas que exhiben las propiedades de superposición de subproblemas que son sólo ligeramente más pequeños [1] y la subestructura óptima (descrito más adelante). En su caso, el método toma mucho menos tiempo que los métodos de ingenuo.
La idea clave detrás de la programación dinámica es bastante sencilla. En general, para resolver un problema dado, tenemos que resolver diferentes partes del problema (subproblemas), a continuación, combinar las soluciones de los subproblemas para alcanzar una solución global. A menudo, muchos de estos subproblemas son realmente lo mismo. El enfoque de programación dinámica tiene por objeto resolver cada subproblema una sola vez, ahorrando una gran cantidad de cálculo. Esto es especialmente útil cuando el número de repetición de subproblemas es exponencialmente grande.
programación dinámica de arriba hacia abajo significa simplemente almacenar los resultados de ciertos cálculos, que luego son utilizados de nuevo ya que el cálculo se completa un sub-problema de un cálculo más grande. hasta dinámicas de programación-parte inferior consiste en la formulación de un cálculo complejo como recursiva serie de cálculos más simples.
No hay comentarios:
Publicar un comentario