Programación Dinámica
La técnica de programación dinámica, resuelve los problemas combinando las soluciones de los subproblemas,
al igual que el enfoque divide y vencerás. (”Programación” en este contexto hace referencia a a un método
y no a un código de computadora). La programación dinámica es aplicable solo cuando los subproblemas no son
independientes, es decir, cuando los subproblemas comparten subsubproblemas. En este contexto, un algoritmo
divide y vencerás realiza más trabajo del necesario, resolviendo repetitivamente los subsubproblemas comunes.
Ejemplo de un algoritmo divide y vencerás: fibonacci
int f;
if (n ==1 || n ==0)
f = 1;
else
f = fibo(n-1) + fibo(n-2);
return f;
}
Estás son las llamadas recursivas que se realizan para n =4
Nota: fib(0) se resuelve 2 veces, fib(1) en 3 ocasiones y fib(2) otro par.
En programación dinámica se resuelve cada subproblema solo una vez y se guardan las respuestas en una tabla, de tal forma que se evita el trabajo de recalcular las respuestas cada vez que el subproblema es encontrado.
int DP_fibo(int n) {
memo[1] = memo[2] = 1; // inicialización para el algoritmo DP
// calculamos los los valores para n>2
for (int i=3; i<=n; i++)
memo[i] = memo[i-1] + memo[i-2];
return memo[n];
}
La programación dinámica es aplicada tipicamente a problemas de optimización. En los que pueden existir muchas posibles soluciones. Cada solución tiene un vlaor, y nosotros deseamos encontrar la solución con valor óptimo. (minimización o maximización). Podemos llamar a tal solución una solución óptima al problema.
El desarrollo de un algoritmo de programación dinámica puede ser descompuesto en una secuencia de cuatro pasos:
- Caracterizar la estructura de una solución óptima.
- Definir recursivamente el valor de una solución óptima.
- Calcular el valor de una solución óptima de la forma bottom-up.
- Construir una solución óptima a partir de la información calculada.
on November 19th, 2009 at 1:03 pm
Muchisimas Gracias por la Información
fue de gran ayuda para un TP qe estaba haciendo..
aparte todo esta muy bien explicado.
abrazo y suerte!! ;D
on August 28th, 2010 at 10:47 pm
This is quite entertaining, thanks