Vistas de página en total

viernes, 21 de febrero de 2014

MEMOIZACIÓN



En uno de mis anteriores post había mencionado el término "memoización" específicamente en el del cálculo del factorial de un número implementado de manera recursiva. Bien ahora veamos en que consiste...
 Esta técnica de optimización suele emplearse sobre todo en algoritmos implementados de manera recursiva, básicamente lo que hace es reducir considerablemente el número de llamadas dentro de una función recursiva, esto evita cálculos innecesarios los cuales ya se habían hecho antes dentro de la función.
Para hacer más gráfica mi explicación tomaré el cálculo de los números de la sucesión Fibonacci.

Cuando tenemos una sucesión de Fibonacci decimos que nuestros casos base son cuando dada una función  fibo(1) es igual a 1, y fibo(0) = 0, visto de mejor forma:

si fibo(0) = 0
ó
si fibo(1) = 1

lo demás es sencillo pues solo calculamos las respuestas para un número (n-1) + (n-2), según la sucesión.
Ya para conocer mejor aquí implementada la sucesión Fibonacci en C de manera recursiva:
int fibo(int n){
   if(n<=0)
      return 0;
   if(n==1)
      return 1;
return fibo(n-1) + fibo(n-2);
}
Aquí tenemos el código de una sucesión Fibonacci pero, si nos ponemos a analizar un poco el problema podemos observar que se harán cálculos de números que posiblemente en otra llamada ya se hayan hecho, por ejemplo para el fibonacci de n = 5, el la primera llamada sería...

1) fibo(4) + fibo(3); //Calculando el fibonacci de 3 y 4

2) Para la llamada con n=4 fibo(3) + fibo(2)  y para n=3 fibo(2) + fibo(1); //Note que se repite el cálculo para la del 3 con la anterior llamada y en esta misma llamada la del 2 se calcula dos veces, así en la próxima recursión tendremos otras ocho llamadas en total.

Esto no suele ser óptimo ya que si lo hacemos para un n con valores muy grandes tendría que hacer el cálculo de cada llamada calculando para su n-1 y n-2 y sobre esas mismas aplicar el mismo procedimiento. 
Para optimizar esto la técnica consiste en memorizar cada respuesta que ya se haya calculado en un arreglo y verificar que no se haya calculado antes. Veamos...

1° Llenamos un arreglo un número "infinito" que jamás llegaremos a obtener en la sucesión de fibonacci.

2° Preguntamos ya en nuestra función recursiva si el número que calculamos es diferente a nuestro número "infinto"(antes puesto en el arreglo), esto nos quiere decir que sí es diferente a ese infinito quiere decir que ya ocupa otro número antes calculado su lugar entonces basta con regresar ese número porque ya ha sido calculado

3° Por último regresamos el calculo de los casos base dentro de nuestro arreglo.

NOTA: dentro de nuestra función el índice del arreglo será nuestra misma n.
El código mejorado queda así...
En el main...
fill(memo,memo+n,INF) // Paso 1. INF es nuestro "inifnito" y la función fill() esta en la librería algorithm de C++ y llena un arreglo de número, para más info, consulte el C++ Reference en internet. ^_^
int fibo(int n){

   if(memo[n] != INF)
      return memo[n];  // Paso 2
   if(n<=0)
      return memo[n] = 0;//Paso 3
   if(n==1)
      return memo[n] = 1; // Paso 3

return memo[n] = fibo(n-1) + fibo(n-2); //Paso 3
}

Así un ejemplo de prueba de escritorio...
1) Nuestro arreglo esta de la siguiente manera:
pos    0       1      2     3      4      5
val   INF   INF   INF   INF   INF   INF

2) Aquí posiblemente ya tenga el calculo para el níumero 1 y 0
pos  0   1     2      3     4      5
val   0   1    INF   INF   INF   INF

Y así se irá llenando nuestro arreglo hasta que llegue a un caso base y de la respuesta pero sin volver a recalcular un número puesto que el paso 2 pregunta que si nuestro número n es diferente a nuestro "infinito" lo cual si es cierto solo devuelve el mismo.
La memoización es una técnica que nos ayuda mucho sobre todo en la Programación Dinámica(dp), porque si hacemos Top-Bottom o sea recursiva una solución podemos memorizar y evitar el recálculo de números...
Eso fue todo por esta sesión y si hay dudas por favor escríbeme a adrian.ipod25@gmail.com, hasta pronto!