subproblemas sobrepostas - Overlapping subproblems
Em ciência da computação , um problema é dito ter subproblemas sobreposição se o problema pode ser dividido em subproblemas que são reutilizados várias vezes ou um algoritmo recursivo para o problema resolve o mesmo subproblema uma e outra vez de sempre gerando novas subproblemas.
Por exemplo, o problema de computação a sequência de Fibonacci exibe subproblems sobrepostas. O problema de computar o n th número de Fibonacci F ( n ), pode ser dividido em sub-problemas de computação os F ( n - 1) e F ( n - 2), e, em seguida, adicionando os dois. O subproblema de computação F ( n - 1) pode ele próprio ser dividido em um subproblema que envolve a computação F ( n - 2). Portanto, o cálculo de F ( n - 2) é reutilizado, e a sequência de Fibonacci assim exposições sobreposição sub-problemas.
Um ingénuo recursiva abordagem para um tal problema geralmente falha devido a uma complexidade exponencial . Se o problema também compartilha uma ótima infra-estrutura de propriedade, programação dinâmica é uma boa maneira de resolver isso.
Exemplo Sequência de Fibonacci em C
Considere o seguinte C código:
#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 */
Quando executado, a fibonacci
função calcula o valor de alguns dos números na sequência muitas vezes, seguindo um padrão que pode ser visualizado por este diagrama de:
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
No entanto, podemos tirar proveito de memoization e alterar a fibonacci
função de fazer uso de fibMem
como assim:
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;
}
Isso é muito mais eficiente porque se o valor r
já foi calculado para um determinado n
e armazenados em fibMem[n - 1]
, a função pode simplesmente devolver o valor armazenado em vez de fazer chamadas de função mais recursiva. Isto resulta num padrão que pode ser visualizado por este diagrama de:
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
A diferença pode não parecer muito significativa com uma N
de 5, mas como seu valor aumenta, a complexidade do original fibonacci
função aumenta exponencialmente, enquanto a versão aumenta revistos mais linearmente.
Veja também
Referências
- ^ Introdução aos Algoritmos , 2ª ed., (Cormen, Leiserson, Rivest e Stein) 2001, p. 327. ISBN 0-262-03293-7 .
- ^ Introdução aos Algoritmos , 3ª ed., (Cormen, Leiserson, Rivest e Stein) 2014, p. 384. ISBN 9780262033848 .
- ^ Programação Dinâmica: sobreposição de subproblemas, Optimal Substructure , MIT Vídeo.