Překrývající se dílčí problémy - Overlapping subproblems

V počítačové vědě se říká , že problém má překrývající se dílčí problémy, pokud lze problém rozdělit na dílčí problémy, které se opakovaně používají opakovaně, nebo rekurzivní algoritmus problému řeší stále stejný dílčí problém, místo aby generoval vždy nové dílčí problémy.

Například problém výpočtu Fibonacciho sekvence vykazuje překrývající se dílčí problémy . Problém výpočtu n- tého Fibonacciho čísla F ( n ) lze rozdělit na dílčí problémy výpočtu F ( n  - 1) a F ( n  - 2) a jejich přidání. Samotný dílčí problém výpočtu F ( n  - 1) lze rozdělit na dílčí problém, který zahrnuje výpočet  F ( n  - 2). Proto je výpočet F ( n  - 2) znovu použit a Fibonacciho sekvence tedy vykazuje překrývající se dílčí problémy.

Naivní rekurzivní přístup k takovému problému obecně selže kvůli exponenciální složitosti . Pokud problém sdílí také optimální vlastnost spodní struktury , je dobrým způsobem, jak to vyřešit , dynamické programování .

Příklad Fibonacciho sekvence v C

Zvažte následující kód 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 */

Při spuštění fibonaccifunkce vypočítá hodnotu některých čísel v sekvenci mnohonásobně podle vzoru, který lze vizualizovat tímto diagramem:

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

Můžeme však využít výhod memoizace a změnit fibonaccifunkci tak, aby se používalo fibMemtakto:

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;
}

To je mnohem efektivnější, protože pokud rjiž byla hodnota pro určitou vypočítána na uložena v ní fibMem[n - 1], může funkce pouze vrátit uloženou hodnotu, místo aby prováděla více rekurzivních volání funkcí. Výsledkem je vzor, ​​který lze vizualizovat tímto diagramem:

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

Rozdíl se nemusí zdát příliš významný s číslem N5, ale jak se jeho hodnota zvyšuje, složitost původní fibonaccifunkce se zvyšuje exponenciálně, zatímco revidovaná verze se zvyšuje lineárněji.

Viz také

• Dynamické programování

Reference