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, fibonaccifunkcja 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ć fibonaccifunkcję wykorzystać fibMemtak:

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ść rzostała już obliczona dla pewnego ni 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 N5, ale w miarę zwiększania wartości, złożoność pierwotnej fibonaccifunkcji wzrasta wykładniczo, natomiast zmienionych wersji bardziej wzrasta liniowo.

Zobacz też

Referencje

  1. ^ Introduction to Algorithms , 2nd ed., (Cormen, Leiserson, Rivest, Stein), 2001, str. 327. ISBN  0-262-03293-7 .
  2. ^ Introduction to Algorithms , 3. wyd., (Cormen, Leiserson, Rivest, Stein), 2014, str. 384. ISBN  9780262033848 .
  3. ^ Programowania dynamicznego: Nakładające podproblemów optymalna podbudowy , MIT Video.