En informática , se dice que un problema tiene subproblemas superpuestos si el problema se puede dividir en subproblemas que se reutilizan varias veces o un algoritmo recursivo para el problema resuelve el mismo subproblema una y otra vez en lugar de generar siempre nuevos subproblemas. [1] [2] [3]
Por ejemplo, el problema de calcular la secuencia de Fibonacci presenta subproblemas superpuestos. El problema de calcular el n- ésimo número de Fibonacci F ( n ) se puede dividir en los subproblemas de calcular F ( n - 1) y F ( n - 2), y luego sumar los dos. El subproblema de calcular F ( n - 1) se puede dividir en sí mismo en un subproblema que implica calcular F ( n - 2). Por tanto, el cálculo de F ( n - 2) se reutiliza y, por tanto, la secuencia de Fibonacci presenta subproblemas superpuestos.
Un enfoque recursivo ingenuo de tal problema generalmente falla debido a una complejidad exponencial . Si el problema también comparte una propiedad de subestructura óptima , la programación dinámica es una buena forma de solucionarlo .
Ejemplo de secuencia de Fibonacci en C
Considere el siguiente código C :
#include #define N 5static int fibMem [ N ];int fibonacci ( int n ) { int r = 1 ; si ( n > 2 ) { r = fibonacci ( n - 1 ) + fibonacci ( n - 2 ); } fibMem [ n - 1 ] = r ; return r ; }void printFibonacci () { int i ; para ( i = 1 ; i <= N ; i ++ ) { printf ( "fibonacci (% d):% d \ n " , i , fibMem [ i - 1 ]); } }int main ( vacío ) { fibonacci ( N ); printFibonacci (); return 0 ; }/ * Salida: fibonacci (1): 1 fibonacci (2): 1 fibonacci (3): 2 fibonacci (4): 3 fibonacci (5): 5 * /
Cuando se ejecuta, la fibonacci
función calcula el valor de algunos de los números en la secuencia muchas veces, siguiendo un patrón que se puede visualizar en este diagrama:
f (5) = f (4) + f (3) = 5 | | | f (3) = f (2) + f (1) = 2 | | | | | f (1) = 1 | | | f (2) = 1 | f (4) = f (3) + f (2) = 3 | | | f (2) = 1 | f (3) = f (2) + f (1) = 2 | | | f (1) = 1 | f (2) = 1
Sin embargo, podemos aprovechar la memorización y cambiar la fibonacci
función para utilizarla fibMem
así:
int fibonacci ( int n ) { int r = 1 ; if ( fibMem [ n - 1 ] ! = 0 ) { r = fibMem [ n - 1 ]; } else { if ( n > 2 ) { r = fibonacci ( n - 1 ) + fibonacci ( n - 2 ); } fibMem [ n - 1 ] = r ; } return r ; }
Esto es mucho más eficiente porque si el valor r
ya se ha calculado para cierto n
y almacenado fibMem[n - 1]
, la función puede simplemente devolver el valor almacenado en lugar de hacer más llamadas de función recursivas. Esto da como resultado un patrón que se puede visualizar mediante este diagrama:
f (5) = f (4) + f (3) = 5 | | f (4) = f (3) + f (2) = 3 | | f (3) = f (2) + f (1) = 2 | | | f (1) = 1 | f (2) = 1
La diferencia puede no parecer demasiado significativa con un valor N
de 5, pero a medida que aumenta su valor, la complejidad de la fibonacci
función original aumenta exponencialmente, mientras que la versión revisada aumenta de manera más lineal.
Ver también
Referencias
- ^ Introducción a los algoritmos , 2ª ed., (Cormen, Leiserson, Rivest y Stein) 2001, p. 327. ISBN 0-262-03293-7 .
- ^ Introducción a los algoritmos , 3ª ed., (Cormen, Leiserson, Rivest y Stein) 2014, p. 384. ISBN 9780262033848 .
- ^ Programación dinámica: subproblemas superpuestos, subestructura óptima , vídeo del MIT.