La programmation dynamique

Numérique et sciences informatiques

I. Introduction

La programmation dynamique, introduite au début des années 1950 par Richard Bellman, est une méthode pour résoudre des problèmes en combinant des solutions de sous-problèmes, tout comme les méthodes de type diviser pour régner.
Un algorithme de programmation dynamique consiste à décomposer un problème en sous-problèmes plus petits, à les résoudre de manière itérative et à stocker les résultats dans une table pour éviter de les recalculer plusieurs fois.
La programmation dynamique s'applique généralement aux problèmes d'optimisation, comme ceux que nous avons vu l'an passé lorsque nous avons étudié les algorithmes gloutons.

II. Principe de la programmation dynamique

Le principe de la programmation dynamique est le suivant :

  1. Décomposer le problème en sous-problèmes plus petits
  2. Résoudre chaque sous-problème de manière itérative
  3. Stocker les résultats dans une table pour éviter de les recalculer plusieurs fois
  4. Combiner les résultats des sous-problèmes pour obtenir la solution au problème initial

III. Exemple : la suite de Fibonacci

Reprenons l'exemple classique de récursivité multiple qu'est celui de la fonction de Fibonacci définie mathématiquement par :

Fibonacci 
def fibonacci(n):
	"""
	Entrée : n - entier positif
	Sortie : entier - valeur de la suite de fibonacci(n)
	"""
	if n < 2:
		return 1
	return fibonacci(n - 1) + fibonacci(n - 2)

Dans la version récursive, pour calculer fibonacci(5), on calcule d’abord fibonacci(4) et fibonacci(3). Pour calculer fibonacci(4), on calcule fibonacci(3) et fibonacci(2). Pour calculer fibonacci(3), on calcule fibonacci(2) et fibonacci(1)... Le déroulement du processus est arborescent comme le montre la figure ci-dessous.

Fibonacci
On remarque que les branches de l’arbre se divise en deux à chaque niveau (sauf en bas de l’arbre, ie. à droite sur la figure), ce qui traduit le fait que la fonction fibonacci s’appelle elle-même deux fois à chaque fois qu’elle est invoquée avec n > 1.
On se rend compte qu'il y a beaucoup d'appels redondants : fib(1) a été lancé 5 fois, fib(2) a été lancé 3 fois, etc.
Ces redondances entraînent un nombre d'appels récursifs qui explose rapidement dès que n est élevé. Par conséquent, les temps de calcul deviennent vite très élevés.

Il existe plusieurs solutions pour obtenir un coût plus raisonnable.
Une solution que nous allons adopter consiste à mémoriser le résultat des calculs une fois qu’ils auront été calculés de manière à ne pas refaire deux fois le même calcul. 

def fibo(n):
	F = [0]*(n+1)
	F[1] = 1
	for i in range(2,n+1) :
		F[i] = F[i-1] + F[i-2]
	return F[n]
Remarque : Cette solution n'est pas récursive.

La fonction fibo(n) prend en entrée un entier n et retourne le n-ème nombre de Fibonacci. La fonction utilise une méthode itérative basée sur la programmation dynamique pour calculer ce nombre.

Les deux premiers nombres de Fibonacci sont définis manuellement (0 et 1). Ensuite, on itère sur les entiers de 2 à n inclus. Pour chaque entier i, on calcule le nombre de Fibonacci correspondant F[n] en utilisant la formule de récurrence F[n] = F[n-2] + F[n-1], où F[n-2] et F[n-1] sont les deux nombres de Fibonacci précédents.

Cet exemple illustre la méthode itérative basée sur la programmation dynamique qui permet de calculer les nombres de Fibonacci de manière efficace et évite la répétition de calculs inutiles.

III. Exemples de problèmes résolus par la programmation dynamique

  1. Alignement de séquences

    2. Le problème de l'alignement de séquences consiste à trouver la meilleure correspondance entre deux séquences de caractères (par exemple, des séquences d'ADN ou de protéines). La programmation dynamique permet de résoudre ce problème en décomposant le calcul de l'alignement optimal en plusieurs sous-problèmes plus petits. On utilise une table pour stocker les résultats intermédiaires et éviter de les recalculer plusieurs fois.

  2. Rendu de monnaie

    3. Le problème du rendu de monnaie consiste à trouver la façon la plus efficace de rendre une somme d'argent donnée en utilisant un ensemble de pièces de monnaie. La programmation dynamique permet de résoudre ce problème en décomposant le calcul de la solution optimale en plusieurs sous-problèmes plus petits. On utilise une table pour stocker les résultats intermédiaires et éviter de les recalculer plusieurs fois.

V. Conclusion

La programmation dynamique est une technique efficace pour résoudre de nombreux problèmes algorithmiques d'optimisation et de combinatoire. Elle permet de réduire considérablement le temps d'exécution de l'algorithme en évitant de recalculer les mêmes résultats plusieurs fois. Cependant, elle peut avoir un coût en mémoire élevé, qui doit être géré avec soin pour éviter les problèmes de mémoire. Les exemples de l'alignement de séquences et du rendu de monnaie sont deux exemples de problèmes qui peuvent être résolus avec la programmation dynamique.


Savoir faire

  • Utiliser la programmation dynamique pour écrire un algorithme.
  • Découvrir l’intérêt de la programmation dynamique pour les recherches d’alignement de séquences.

Fiche de cours