Chevauchement des sous-problèmes - Overlapping subproblems

En informatique , on dit qu'un problème a des sous - problèmes qui se chevauchent si le problème peut être décomposé en sous-problèmes qui sont réutilisés plusieurs fois ou si un algorithme récursif pour le problème résout le même sous-problème à plusieurs reprises plutôt que de toujours générer de nouveaux sous-problèmes.

Par exemple, le problème du calcul de la séquence de Fibonacci présente des sous-problèmes qui se chevauchent. Le problème du calcul du n ème nombre de Fibonacci F ( n ), peut être décomposé en sous-problèmes de calcul F ( n  - 1) et F ( n  - 2), puis addition des deux. Le sous-problème de calcul F ( n  - 1) peut lui-même être décomposé en un sous-problème qui implique le calcul de  F ( n  - 2). Par conséquent, le calcul de F ( n  - 2) est réutilisé, et la séquence de Fibonacci présente donc des sous-problèmes qui se chevauchent.

Une approche naïve récursive d'un tel problème échoue généralement en raison d'une complexité exponentielle . Si le problème partage également une propriété de sous-structure optimale , la programmation dynamique est un bon moyen de le résoudre .

Exemple de séquence de Fibonacci en C

Considérez le code C suivant: 

#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 */

Lorsqu'elle est exécutée, la fibonaccifonction calcule la valeur de certains des nombres de la séquence plusieurs fois, en suivant un modèle qui peut être visualisé par ce diagramme: 

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

Cependant, nous pouvons profiter de la mémorisation et changer la fibonaccifonction pour utiliser fibMemcomme ceci: 

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

C'est beaucoup plus efficace car si la valeur ra déjà été calculée pour un certain net stockée dans fibMem[n - 1], la fonction peut simplement renvoyer la valeur stockée plutôt que de faire des appels de fonction plus récursifs. Il en résulte un modèle qui peut être visualisé par ce diagramme: 

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

La différence peut ne pas sembler trop significative avec un Nde 5, mais à mesure que sa valeur augmente, la complexité de la fibonaccifonction d' origine augmente de manière exponentielle, tandis que la version révisée augmente de manière plus linéaire.

Voir également

Les références

  1. ^ Introduction aux algorithmes , 2e éd., (Cormen, Leiserson, Rivest et Stein) 2001, p. 327. ISBN  0-262-03293-7 .
  2. ^ Introduction aux algorithmes , 3e éd., (Cormen, Leiserson, Rivest et Stein) 2014, p. 384. ISBN  9780262033848 .
  3. ^ Programmation dynamique: sous-problèmes qui se chevauchent, sous-structure optimale , vidéo MIT.