Nakładające podproblemów - Overlapping subproblems
W informatyce , A problemem jest powiedziane, że nakładających podproblemów czy problem może być podzielone na podproblemów które są wykorzystywane wielokrotnie lub rekurencyjny algorytm dla problemu rozwiązuje samą subproblem kółko zamiast zawsze generowania nowych podproblemów.
Na przykład, problem obliczania Fibonacciego wykazuje nakładających podproblemów. Problem obliczania n th numer Fibonacciego F ( n ), może być podzielony na podproblemów z obliczania F ( n - 1) i F ( n - 2), a następnie dodanie dwóch. Subproblem obliczania F ( n - 1), może być sam podzielony na subproblem że obejmuje obliczeniowej F ( n - 2). W związku z tym, obliczenie F ( n - 2), jest wykorzystywany, a tym samym wykazuje sekwencję Fibonacciego nakładania podproblemów.
Naiwny rekurencyjnej podejście do takiego problemu zazwyczaj nie z powodu wykładniczej złożoności . Jeśli problem nie podziela również optymalne podbudowa nieruchomości, programowanie dynamiczne jest dobrym sposobem, aby się dogadać.
Fibonacciego przykład w C
Rozważmy następujący C kod:
#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 */
Gdy wykonywany, fibonacci
funkcja oblicza wartość niektórych liczby w sekwencji wiele razy, zgodnie z wzorem, który może być widoczne przez to rysunku:
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
Możemy jednak skorzystać z memoization i zmienić fibonacci
funkcję wykorzystać fibMem
tak:
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;
}
Jest to o wiele bardziej efektywne, ponieważ jeśli wartość r
została już obliczona dla pewnego n
i przechowywane w fibMem[n - 1]
, funkcja może po prostu wrócić zapamiętanej wartości zamiast dokonywania bardziej rekurencyjnych wywołań funkcji. Powoduje to w układzie, które mogą być wizualizowane w tym schemacie:
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
Różnica nie może wydawać się zbyt znaczące ze związkiem N
5, ale w miarę zwiększania wartości, złożoność pierwotnej fibonacci
funkcji wzrasta wykładniczo, natomiast zmienionych wersji bardziej wzrasta liniowo.
Zobacz też
Referencje
- ^ Introduction to Algorithms , 2nd ed., (Cormen, Leiserson, Rivest, Stein), 2001, str. 327. ISBN 0-262-03293-7 .
- ^ Introduction to Algorithms , 3. wyd., (Cormen, Leiserson, Rivest, Stein), 2014, str. 384. ISBN 9780262033848 .
- ^ Programowania dynamicznego: Nakładające podproblemów optymalna podbudowy , MIT Video.