(Wikipediazo)En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas.
Decir que un problema tiene subproblemas superpuestos es decir que se usa un mismo subproblema para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada término supone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces.
Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama memoización (no confundir con memorización; en inglés es llamado memoization, véase en). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio.
Comenzando con el pseudocódigo:
FUNC Fibonacci (↓n: NATURAL): NATURAL
VARIABLES
tabla: ARRAY [0..n] DE NATURALES
i: NATURAL
INICIO
SI n = 0 ENTONCES
DEVOLVER 0
SINOSI n = 1 ENTONCES
DEVOLVER 1
SINO
tabla[0] := 0
tabla[1] := 1
PARA i = 2 HASTA n HACER
tabla[i] := tabla[i-1] + tabla[i-2]
FINPARA
DEVOLVER tabla[n]
FINSI
FIN
Una implementación en C de este algoritmo es la siguiente (he cambiado los tipos de dato para que se puedan calcular valores más grandes):
long long fibonacciArreglo(int n) {
long long * lista;
if(n == 0) return 0;
if(n == 1) return 1;
lista = (long long *) malloc(sizeof(long long) * n);
lista[0] = 0;
lista[1] = 1;
int i;
for (i = 2; i <= n; i++) {
lista[i] = lista[i-1] + lista[i-2];
}
return lista[n];
}
Como podemos ver, se reservan n espacios de memoria para almacenar todos los valores de la sucesión, aunque solamente se emplean dos de estos valores a la hora de cálcular el siguente número. Lo cual deriva en un "desperdicio" de memoria.
Es por eso que basándome en el enunciado que está más arriba en negritas, pensé que implementar una cola sería una opción para ahorrar espacio, podemos agregar dinámicamente los nuevos valores y quitar los que ya no usaremos, de tal manera solo tendríamos en memoria los valores necesarios para calcular el siguiente número en la sucesión. El código queda como sigue:
long long fibonacciCola(int n) {
Cola cola;
if (n == 0) return 0;
if (n == 1) return 1;
creaLista(&cola);
formar(&cola, 0);
formar(&cola, 1);
int i;
for (i = 2; i <= n; i++) {
// Quitamos el elemento menos reciente
long long fi1 = atender(&cola);
// Obtenemos el valor del siguiente más reciente
long long fi2 = valorPrincipio(&cola);
// Almacenamos el resultado en la cola
formar(&cola, fi1 + fi2);
}
return valorFinal(&cola);
}
De esta forma aseguramos que para cualquier tamaño de
n solo se ocupen a lo más 3 espacios de memoria.
El código está disponible en la sección de extras del proyecto
analizando-algo
¡Saludos!
@fferegrino :)
