Subprobleme care se suprapun - Overlapping subproblems

În informatică , se spune că o problemă are subprobleme care se suprapun dacă problema poate fi descompusă în subprobleme care sunt refolosite de mai multe ori sau un algoritm recursiv pentru problemă rezolvă aceleași subprobleme, mai degrabă, decât să genereze întotdeauna noi subprobleme.

De exemplu, problema calculării secvenței Fibonacci prezintă subprobleme suprapuse. Problema de calcul a n - lea numar Fibonacci F ( n ), poate fi descompusă în subproblemelor de calcul F ( n  - 1) și F ( n  - 2), și apoi adăugarea celor două. Subproblema de calcul F ( n  - 1) poate fi ea însăși defalcat într-un subproblem care implică calcul  F ( n  - 2). Prin urmare, calculul lui F ( n  - 2) este reutilizat, iar secvența Fibonacci prezintă astfel subprobleme suprapuse.

O abordare recursivă naivă a unei astfel de probleme eșuează în general din cauza unei complexități exponențiale . Dacă problema împărtășește și o proprietate optimă de substructură , programarea dinamică este o modalitate bună de rezolvare a acesteia.

Exemplu de secvență Fibonacci în C

Luați în considerare următorul cod 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 */

Când este executată, fibonaccifuncția calculează valoarea unora dintre numerele din secvență de multe ori, urmând un model care poate fi vizualizat prin această diagramă:

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

Cu toate acestea, putem profita de memorare și de a schimba fibonaccifuncția pentru a folosi fibMemastfel:

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

Acest lucru este mult mai eficient, deoarece dacă valoarea ra fost deja calculată pentru un anumit nși stocată în fibMem[n - 1], funcția poate doar să returneze valoarea stocată, mai degrabă decât să efectueze apeluri funcționale mai recursive. Rezultă un model care poate fi vizualizat prin această diagramă:

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

Diferența poate să nu pară prea semnificativă cu N5, dar pe măsură ce valoarea acesteia crește, complexitatea fibonaccifuncției originale crește exponențial, în timp ce versiunea revizuită crește mai liniar.

Vezi si

• Programare dinamică

Referințe