Programmation dynamique

Illustration par l'exemple

La suite de Fibonacci

Afin d'illustrer nos propos concernant le fonctionnement des méthodes de programmation dynamique, nous allons résoudre un exercice d'initiation à l'algorithmique bien connu : le calcul d'un nombre de la suite de Fibonnaci.

Le problème est de calculer le nème nombre de la suite de Fibonacci, laquelle est déterminée de la façon suivante : 

fibo(0) = 1
fibo(1) = 1
fibo(n) = fibo(n-1) + fibo(n-2)

avec n ∈ ℕ

Définition de la suite de Fibonacci en pseudo-code

Cette fonction n'est définie que sur l’ensemble des nombres naturels (nombres entiers positifs), d'où n ∈ ℕ.

L'algorithme naïf

Voici tout d'abord comment serait implémentée la fonction de calcul d'un nombre de la suite de Fibonacci naïvement (c'est-à-dire, la transcription intuitive de sa définition) :

function fibo(n) {
	if (n <= 1) {
		return 1
	} else {
		return (fibo(n-1) + fibo(n-2))
	}
}

Algorithme naïf en pseudo-code

Nous remarquons rapidement que la complexité algorithmique de cette fonction est exponentielle — c'est déplorable algorithmiquement. La raison de cette inefficacité se résume en fait à la multiplicité de calcul d’un même nombre. Nous nous appuyons sur le schéma suivant pour illustrer cela :


L'arbre des appels récursifs à la fonction Fibo

Comme c'est représenté sur la figure ci-dessus, nous constatons que pour déterminer le résultat de la fonction Fibo avec l'argument 4, l'algorithme réutilisera récurvisement cette fonction avec les arguments 3 et 2 dans un premier temps... Mais cela ne s'arrête pas là ! Pour obtenir le résultat de Fibo(3), il se basera sur un nouvel appel à Fibo(2) ainsi qu'à Fibo(1), puis chaque appel à Fibo(2) nécessitera encore l'exécution récursive des fonctions Fibo avec les arguments 1 et 0...

De cette façon, à l'aide du schéma ci-dessus, nous comprenons rapidement que cette solution n'est pas efficace.

Vers une solution plus efficace

La clef d'une solution plus efficace serait de s'affranchir de la multiplicité des résolutions du même sous-problème. On améliore de loin la complexité temporelle si, une fois calculé, on sauvegarde un résultat — dans un tableau par exemple — puis que, au besoin, on le reprend depuis ce tableau. Cette remarque nous amène à la solution suivante :

function fibo(n) { 
	if (table[n] existe) {
		return table[n]
	}
	if (n <= 2) {
		return 1
	} else {
		res = fibo(n-1) + fibo(n-2)
		table[n] = res
		return res
	}
}

Algorithme selon une fonction à mémoire en pseudo-code

Cette approche de résolution est connue sous le nom de fonction à mémoire, qui est très liée à la programmation dynamique.

Application de l'approche dynamique

À présent, en se basant sur notre algorithme utilisant une fonction à mémoire et en en supprimant la récursivité, nous écrivons cet algorithme de manière ascendante, dans une forme typique de la programmation dynamique :

function fibo(n) { 
	table[0] = 1
	table[1] = 1
	
	for (i=2 ; i<=n ; i++) {
		table[i] = table[i-1] + table[i-2]
	}
	return table[n]
}

Algorithme au format "programmation dynamique" en pseudo-code

De cette façon, la complexité de notre algorithme est à présent linéaire : c'est un progrès formidable ! Nous pourrions obtenir de bien meilleures performances encore, mais ce n'est pas le sujet de cette présentation.

En conclusion

Cette démonstration avait pour but d'illustrer les grands principes de la programmation dynamique et sa mise en place dans un problème simple. En résumé :

Cela n’est pas sans nous rappeler les méthodes diviser & régner, mais c’est en fait tout à fait différent, puisqu'en programmation dynamique :