Programacion dinamica

PROGAMACION DINAMICA
INTRODUCCION
La programación dinámica es utilizada en compiladores, consiste en solucionar cierto problema diviendolo en subproblemas más sencillos, calculando sus resultadosy almacenándolos. Estos resultados posteriormente se utilizan para la resolución del problema final.
Almacenar resultados de subproblemas es una gran ventaja en cálculos dónde se repiten las mismasoperación múltiples veces, mediante el método de la programación dinámica estas operaciones sólo se realizan una vez y se guarda la solución.
Se dice de la programación dinámica que es un método pararesolver problemas que exhiben propiedades de problemas sobrepuestos y estructura óptima.
Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar lasolución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos losvértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:1. Dividir el problema en subproblemas más pequeños.
2. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
3. Usar estas soluciones óptimas para construiruna solución óptima al problema original.
PRINCIPIO DE OPTIMIDAD
Cuando hablamos de optimizar nos referimos a buscar alguna de las menores soluciones de entre muchas alternativas posibles. Dichoproceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución incorrecta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión quedebe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz. nudo,...