La programmation dynamique

Introduction

La programmation dynamique est une méthode permettant de résoudre des problèmes d'optimisation, inventée par Richard Bellman dans les années 1950.

Son fonctionnement consiste à :

• Diviser le problème initial en sous-problèmes ;
• Résoudre individuellement chaque sous-problème ;
• Stocker les résultats obtenus lors de la résolution des sous-problèmes, pour les réutiliser.

Règle générale de la programmation dynamique

À retenir

Pour reconnaître et résoudre un problème avec la programmation dynamique, on suit généralement les étapes suivantes :

1. Identifier un problème d'optimisation (minimum, maximum, nombre de façons, etc.) ;
2. Décomposer le problème en sous-problèmes plus petits ;
3. Vérifier qu'il y a des sous-problèmes qui se répètent ;
4. Définir une relation de récurrence entre les sous-problèmes ;
5. Mémoriser les résultats (mémoïsation ou tableau) ;
6. Construire la solution finale à partir des sous-problèmes.

Deux approches possibles

Il existe deux grandes façons d'implémenter la programmation dynamique :

• Top-down (mémoïsation) : on part du problème initial et on utilise la récursion en stockant les résultats déjà calculés ;
• Bottom-up (tabulation) : on construit directement les solutions des plus petits sous-problèmes jusqu'au problème final.

Exemple d'application avec Fibonacci

La suite de Fibonacci est un exemple classique permettant d'illustrer la programmation dynamique.

La suite de Fibonacci, dans sa version récursive, n'est pas optimale. On se rend vite compte qu'un peu avant le calcul du 30ème terme, le programme met plusieurs minutes à obtenir un résultat.

On a le programme récursif suivant :

def fibonacci(n):
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

Si on calcule le 6ème terme de cette suite, on peut obtenir l'arbre suivant :

De nombreuses branches

On peut remarquer qu'il existe plusieurs fois les mêmes appels de fonction, dans plusieurs branches de l'arbre.

En calculant le temps d'exécution de cette fonction avec plusieurs termes, on peut obtenir cette courbe :

Complexité

Dans cet exemple, la version récursive de la suite de fibonacci offre une complexité temporelle et spatiale exponentielle.

Mémoïsation

Mémoïser

La mémoïsation consiste à stocker les résultats déjà calculés afin d'éviter de refaire plusieurs fois le même calcul.

C'est le cœur de la programmation dynamique : au lieu de recalculer un sous-problème, on réutilise directement sa valeur déjà connue.

On utilise généralement une structure de données adaptée (liste, dictionnaire, matrice...) pour stocker ces résultats.

Dans le cas de la suite de Fibonacci, la mémoïsation s'utilise avec une liste, où chaque indice de la liste correspond à un terme de la suite, et chaque élément de liste contient la valeur calculée de la suite, au terme donné.

Exemple

On souhaite calculer le 6ème terme de la suite. Initialement avec la version récursive, on aurait, en terme de calcul, l'arbre donné plus haut.
Avec la mémoïsation, l'arbre ressemblerait à ceci :

Où chaque noeud ne correspond qu'à un accès dans la liste à la valeur du terme correspondant à l'indice.

Avec la liste, on aurait à l'initialisation :

Indice (terme)	0	1
Valeur	0	1

Puis, pour chaque terme à calculer en plus, on ajouterait dans cette liste un nouvel élément, qui aurait pour valeur la somme des 2 éléments précédents :

• Terme 2 = Terme 1 + Terme 0

  Indice (terme)	0	1	2
  Valeur	0	1	1

• Terme 3 = Terme 2 + Terme 1

  Indice (terme)	0	1	2	3
  Valeur	0	1	1	2

• Terme 4 = Terme 3 + Terme 2

  Indice (terme)	0	1	2	3	4
  Valeur	0	1	1	2	3

• Terme 5 = Terme 4 + Terme 3

  Indice (terme)	0	1	2	3	4	5
  Valeur	0	1	1	2	3	5

• Terme 6 = Terme 5 + Terme 4

  Indice (terme)	0	1	2	3	4	5	6
  Valeur	0	1	1	2	3	5	8