Programacion Dinamica Método general
ReTrOwArIoR12 de Octubre de 2011
420 Palabras (2 Páginas)1.808 Visitas
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 de decisiones.
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 para problemas más pequeños.
Los algoritmos divide y vencerás están dentro de los métodos descendentes.
Empezar con el problema original y descomponer en pasos sucesivos en problemas 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.
La programación dinámica se basa en el Principio de Optimalidad 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.
Aspectos a definir en un algoritmo de programación dinámica:
• Ecuación recurrente, para calcular la solución de los problemas grandes en función de los problemas más
pequeños.
• Determinar los casos base.
• Definir las tablas utilizadas por el algoritmo, y cómo son rellenadas.
• Cómo se recompone la solución global a partir de los valores de las tablas.
Características de las Aplicaciones de Programación Dinámica
CARACTERÍSTICA 1
El problema se puede dividir en etapas; cada etapa requiere una decisión.
CARACTERÍSTICA 2
Cada etapa tiene un número de estados asociados con ella.
Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.
CARACTERÍSTICA 3
La decisión tomada en cualquier etapa indica cómo se transforma el estado en la etapa actual en el estado
en la siguiente etapa.
En muchos problemas, una decisión no determina con certeza el estado de la siguiente etapa; en lugar de
ello, la decisión actual sólo determina la distribución de probabilidad del estado en la etapa siguiente.
CARACTERÍSTICA 4
Dado el estado actual, la decisión óptima para cada una de las etapas restantes no debe depender de
estados previamente alcanzados o de decisiones previamente tomadas.
A esta idea se le conoce como principio de optimalidad.
CARACTERÍSTICA 5
Si los estados del problema se han clasificado en uno de T etapas, debe haber una fórmula recursiva que
relacione el costo o recompensa durante las etapas con el costo o recompensa de las etapas
En esencia, la fórmula recursiva formaliza el procedimiento de retroceso.
La estrategia bottom-up, consiste en resolver primero los subproblemas más pequeños, almacenar su solución, y
luego resolver los problemas más complejos, usando los resultados almacenados.
...