Programacion Dinamica
Páginas: 10 (2384 palabras)
Publicado: 4 de febrero de 2013
DEFINICIÓN DE PROGRAMACIÓN DINÁMICA
La programación dinámica es un método de optimización del cálculo de problemas.
La programación dinámica es utilizada en compiladores, que consiste en solucionar cierto problema diviendolo en subproblemas más sencillos, calculando sus resultados y almacenándolos. Estos resultados posteriormente se utilizan para la resolución del problema final.
Almacenarresultados de subproblemas es una gran ventaja en cálculos dónde se repiten las mismas operació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 para resolver problemas que exhiben propiedades de problemas sobrepuestos y estructura óptima.Características de un Problema de Programación Dinámica
Para que un problema pueda ser resuelto con la técnica de programación dinámica, debe
cumplir con ciertas características:
Naturaleza secuencial de las decisiones: El problema puede ser dividido en etapas.
Cada etapa tiene un numero de estados asociados a ella.
La decisión óptima de cada etapa depende solo del estado actual y no de lasdecisiones anteriores.
La decisión tomada en una etapa determina cual será el estado de la etapa siguiente.
En síntesis, la política óptima desde un estado s de la etapa k a la etapa final esta constituida por una decisión que transforma s en un estado s0 de la etapa k +1 y por la política óptima
desde el estado s0 hasta la etapa final.http://webysw.blogspot.mx/2009/04/caracteristicas-de-un-problema-de.html
2.2 ejemplos Programación Dinámica — Presentation Transcript
* 1. Programación dinámica Método general. Análisis de tiempos de ejecución. Ejemplos de aplicación. 3.1. Problema del cambio de monedas. 3.2. Problema de la mochila 0/1.
* 2. Método general La programación dinámica se suele utilizar en problemas de optimización , donde una solución está formada por una serie dedecisiones. Igual que la técnica divide y vencerás , resuelve el problema original combinando las soluciones para subproblemas más pequeños. Sin embargo, la programación dinámica no utiliza recursividad, sino que almacena los resultados de los subproblemas en una tabla , calculando primero las soluciones para los problemas pequeños. Con esto se pretende evitar la repetición de cálculos paraproblemas más pequeños.
* 3. Método general Ejemplo. Cálculo de los números de Fibonacci. Con método recursivo Fibonacci (n: integer) Si n<2 Devolver 1 Sino Devolver Fibonacci (n-1) + Fibonacci (n-2) Problema: Muchos cálculos están repetidos, tiempo de ejec. exponencial. Solución: Calcular los valores de menor a mayor empezando por 0, e ir guardando los resultados en una tabla. Con programacióndinámica Fibonacci (n: integer) T[0] = 0; T[1] = 1 para i = 2,3, ...,n T[i] = T[i-1] + T[i-2] Devolver T[n] Se utiliza la misma fórmula que en la versión anterior, pero de forma más inteligente. El tiempo de ejecución es (n).
* 4. Método general Los algoritmos divide y vencerás están dentro de los métodos descendentes . Empezar con el problema original y descomponer en pasos sucesivos enproblemas de menor tamaño. Partiendo del problema grande, descendemos hacia problemas más sencillos. La programación dinámica , por el contrario, es un método ascendente : Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla) y después vamos combinando para resolver los problemas más grandes.
* 5. Método general La programación dinámica se basa en el Principio deOptimalidad de Bellman : cualquier subsecuencia de una secuencia óptima debe ser, a su vez, una secuencia óptima. Para cada problema deberíamos comprobar si es aplicable el principio de optimalidad. Ejemplo . 2 B 9 A D 3 C 7 Camino óptimo de A a D: A-C-D, de longitud 10 Camino óptimo de A al siguiente nivel: A-B, de longitud 2, y después B-D de longitud 9. Total: A-B-D, de longitud 11 ¿Cumple el...
La programación dinámica es un método de optimización del cálculo de problemas.
La programación dinámica es utilizada en compiladores, que consiste en solucionar cierto problema diviendolo en subproblemas más sencillos, calculando sus resultados y almacenándolos. Estos resultados posteriormente se utilizan para la resolución del problema final.
Almacenarresultados de subproblemas es una gran ventaja en cálculos dónde se repiten las mismas operació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 para resolver problemas que exhiben propiedades de problemas sobrepuestos y estructura óptima.Características de un Problema de Programación Dinámica
Para que un problema pueda ser resuelto con la técnica de programación dinámica, debe
cumplir con ciertas características:
Naturaleza secuencial de las decisiones: El problema puede ser dividido en etapas.
Cada etapa tiene un numero de estados asociados a ella.
La decisión óptima de cada etapa depende solo del estado actual y no de lasdecisiones anteriores.
La decisión tomada en una etapa determina cual será el estado de la etapa siguiente.
En síntesis, la política óptima desde un estado s de la etapa k a la etapa final esta constituida por una decisión que transforma s en un estado s0 de la etapa k +1 y por la política óptima
desde el estado s0 hasta la etapa final.http://webysw.blogspot.mx/2009/04/caracteristicas-de-un-problema-de.html
2.2 ejemplos Programación Dinámica — Presentation Transcript
* 1. Programación dinámica Método general. Análisis de tiempos de ejecución. Ejemplos de aplicación. 3.1. Problema del cambio de monedas. 3.2. Problema de la mochila 0/1.
* 2. Método general La programación dinámica se suele utilizar en problemas de optimización , donde una solución está formada por una serie dedecisiones. Igual que la técnica divide y vencerás , resuelve el problema original combinando las soluciones para subproblemas más pequeños. Sin embargo, la programación dinámica no utiliza recursividad, sino que almacena los resultados de los subproblemas en una tabla , calculando primero las soluciones para los problemas pequeños. Con esto se pretende evitar la repetición de cálculos paraproblemas más pequeños.
* 3. Método general Ejemplo. Cálculo de los números de Fibonacci. Con método recursivo Fibonacci (n: integer) Si n<2 Devolver 1 Sino Devolver Fibonacci (n-1) + Fibonacci (n-2) Problema: Muchos cálculos están repetidos, tiempo de ejec. exponencial. Solución: Calcular los valores de menor a mayor empezando por 0, e ir guardando los resultados en una tabla. Con programacióndinámica Fibonacci (n: integer) T[0] = 0; T[1] = 1 para i = 2,3, ...,n T[i] = T[i-1] + T[i-2] Devolver T[n] Se utiliza la misma fórmula que en la versión anterior, pero de forma más inteligente. El tiempo de ejecución es (n).
* 4. Método general Los algoritmos divide y vencerás están dentro de los métodos descendentes . Empezar con el problema original y descomponer en pasos sucesivos enproblemas de menor tamaño. Partiendo del problema grande, descendemos hacia problemas más sencillos. La programación dinámica , por el contrario, es un método ascendente : Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla) y después vamos combinando para resolver los problemas más grandes.
* 5. Método general La programación dinámica se basa en el Principio deOptimalidad de Bellman : cualquier subsecuencia de una secuencia óptima debe ser, a su vez, una secuencia óptima. Para cada problema deberíamos comprobar si es aplicable el principio de optimalidad. Ejemplo . 2 B 9 A D 3 C 7 Camino óptimo de A a D: A-C-D, de longitud 10 Camino óptimo de A al siguiente nivel: A-B, de longitud 2, y después B-D de longitud 9. Total: A-B-D, de longitud 11 ¿Cumple el...
Leer documento completo
Regístrate para leer el documento completo.