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 fibonaccifunció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 fibonaccifunción para utilizarla fibMemasí:

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 rya se ha calculado para cierto ny 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 Nde 5, pero a medida que aumenta su valor, la complejidad de la fibonaccifunción original aumenta exponencialmente, mientras que la versión revisada aumenta de manera más lineal.

Ver también

Referencias

  1. ^ Introducción a los algoritmos , 2ª ed., (Cormen, Leiserson, Rivest y Stein) 2001, p. 327. ISBN  0-262-03293-7 .
  2. ^ Introducción a los algoritmos , 3ra ed., (Cormen, Leiserson, Rivest y Stein) 2014, p. 384. ISBN  9780262033848 .
  3. ^ Programación dinámica: subproblemas superpuestos, subestructura óptima , vídeo del MIT.