Programmation dynamique

Concept créé au début des années 1950 par Richard Bellman. Il explique lui-même que la société pour laquelle il travaillait dépendait des décisions d'un secrétaire à la défense, donc un représentant de l'armée, qui ne voulait pas entendre parler de recherche ou de mathématiques. Richard Bellman a donc choisi un terme un peu vague, qui pouvait, en forçant un peu, décrire ce qu'il faisait, mais qui surtout faisait plaisir au secrétaire à la défense un peu obtus. C'est de là que vient le nom programmation dynamique – l'idée est que le mot dynamique parle bien à un militaire.

La suite de Fibonacci est définie par:

• $F(0) = 1$,
• $F(1) = 1$,
• pour $n \geqslant 2$, $F(n) = F(n-1) + F(n-2)$.

On pourrait – comme on l'a fait dans le cours sur la récursivité – programmer en Python :

# version naïve
def F(n):
    if n <= 1:
        return 1
    return F(n-1) + F(n-2)

C'est simple et cela suit de près la définition mathématique de la suite.

Supposons que l'on veuille calculer $F(5)$.

Cet arbre représente le calcul et les appels récursifs.

• Pour calculer $F(5)$ il faut calculer $F(4)$ et $F(3)$.
• $F(4)$ nécessite lui-même le calcul de $F(3)$ et $F(2)$.
• Et ainsi de suite…

On voit que cette façon d'organiser le calcul est peu performante puisque l'on va calculer plusieurs fois la même chose. Par exemple, on calcul 5 fois $F(1)$ et 3 fois $F(2)$ !

Imaginez la perte de temps pour calculer $F(1\,000)$ ou $F(1\,000\,000)$…

Il faudrait donc organiser notre suite de calculs pour ne pas faire plusieurs fois le même calcul. C'est tout le principe de la programmation dynamique.

On sait que le calcul de $F(n)$ nécessitera de calculer tous les $F(i)$ avec $0 \leqslant i < n$. Le calcul de ces $F(i)$ sont autant de sous-problèmes que l'on va traiter dans le sens croissant en sauvegardant les réponses.

# version dynamique
def F(n):
    tab_F = [1, 1] # on sait que F(0) = F(1) = 1
    for i in range(2, n+1):
        F_i = tab_F[i-1] + tab_F[i-2]
        tab_F.append(F_i)
    return tab_F[-1] # renvoie le dernier calculé

Dans cette fonction on augmente la taille du tableau (append) à chaque itération de la boucle for. Ce genre d'opération est long. On pourrait améliorer les choses en créant dès le début un tableau avec la bonne taille.

# version dynamique améliorée
def F(n):
    tab_F = [0]*(n+1) # tableau de n+1 éléments, tous à 0
    tab_F[0] = 1 # on sait que F(0) = 1
    tab_F[1] = 1 # on sait que F(1) = 1
    for i in range(2, n+1):
        tab_F[i] = tab_F[i-1] + tab_F[i-2] # plus besoin de append
    return tab_F[-1] # renvoie le dernier calculé

L'exécution de cette version est plus rapide.

On va noter $C_{rec}(n)$ on évaluation grossière du nombre d'instructions nécessaires du calcul de $F(n)$ avec la version récurrente.

• On peut poser que $F(0)$ et $F(1)$ sont calculés en une instruction, donc $C_{rec}(0) = C_{rec}(1) = 1$.
• Pour $n \geqslant 2$, $F(n) = F(n-1) + F(n-2)$, on peut donc estimer que le coût du calcul de $F(n)$ est égal au coût du calcul de $F(n-1)$ plus le coût de calcul de $F(n-2)$ plus l'addition donc $C_{rec}(n) = C_{rec}(n-1) + C_{rec}(n-2) + 1$.

On peut prouver que, si $a = \frac{1 - \sqrt{5}}{2} \simeq -0,6$ et $b = \frac{1 + \sqrt{5}}{2} \simeq 1,6$ alors $C_{rec}(n) = \frac{2}{\sqrt{5}} \cdot \left(b^{n+1} - a^{n+1}\right) - 1$.

Donc pour $n \to +\infty$, $C_{req}(n) \simeq 1,4 \times 1,6^n$. C'est une croissance exponentielle.

Dans sa version dynamique, on peut dire que le calcule de $F(n)$ nécessite

• la lecture de $F(n-1)$ dans le tableau,
• la lecture de $F(n-2)$ dans le tableau,
• le calcul de la somme,
• l'écriture de $F(n)$ dans le tableau.

Donc $C_{dyn}(n) \simeq 4\,n$.

Puisque la version récurrente est en $1,6^n$ et la version dynamique en $n$, quels que soient les coefficients, quand $n \nearrow$, le temps nécessaire pour la version récurrente devient beaucoup plus grand. Donc avec des problèmes de grande taille, l'approche dynamique sera avantageuse.