Subproblemas superpuestos - Overlapping subproblems
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.
Por ejemplo, el problema de calcular la secuencia de Fibonacci presenta subproblemas superpuestos. El problema de calcular el número n 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 lo tanto, el cálculo de F ( n - 2) se reutiliza y 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 manera de resolverlo.
Ejemplo de secuencia de Fibonacci en C
Considere el siguiente código C :
#include <stdio.h>
#define N 5
static int fibMem[N];
int fibonacci(int n) {
int r = 1;
if (n > 2) {
r = fibonacci(n - 1) + fibonacci(n - 2);
}
fibMem[n - 1] = r;
return r;
}
void printFibonacci() {
int i;
for (i = 1; i <= N; i++) {
printf("fibonacci(%d): %d\n", i, fibMem[i - 1]);
}
}
int main(void) {
fibonacci(N);
printFibonacci();
return 0;
}
/* Output:
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 , 3ra ed., (Cormen, Leiserson, Rivest y Stein) 2014, p. 384. ISBN 9780262033848 .
- ^ Programación dinámica: subproblemas superpuestos, subestructura óptima , vídeo del MIT.