Programmation dynamique : cours de Terminale NSI

Tu connais déjà la méthode diviser pour régner : on coupe un problème en morceaux, on résout chaque morceau, puis on assemble. Le tri fusion en est l'exemple typique. Cette méthode marche très bien quand les morceaux sont indépendants. Mais que se passe-t-il quand deux morceaux demandent de refaire exactement le même calcul ?

C'est le cas qui nous intéresse dans ce chapitre. La programmation dynamique est une technique de conception d'algorithmes, pensée pour les problèmes d'optimisation, qui apparaît au début des années 1950 avec Richard Bellman ⁶. À l'époque, le mot « programmation » voulait dire planification et ordonnancement, pas écriture de code ⁶. Le nom peut donc surprendre : il n'a aucun rapport avec une façon de programmer « dynamiquement » en Python.

La méthode a séduit très vite l'industrie, où beaucoup de calculs économiques suivaient cette logique : piloter des procédés chimiques ou gérer des stocks, par exemple ⁶. Dans le programme de terminale NSI, elle fait partie de la partie algorithmique, aux côtés des algorithmes sur les arbres et les graphes et de la méthode diviser pour régner.

Prenons l'exemple classique, souvent utilisé pour introduire le sujet : la suite de Fibonacci ⁶. Elle est définie par $F_0 = 0$, $F_1 = 1$ et, pour $n \geq 2$, $F_n = F_{n-1} + F_{n-2}$ ⁶. Les premiers termes sont donc $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55\ldots$

La définition se traduit tout de suite en fonction récursive :

def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n - 1) + fib(n - 2)

C'est un algorithme inefficace : quand un même sous-problème se présente plusieurs fois, diviser pour régner perd son efficacité ⁶. Voyons pourquoi sur $F_5$.

Le remède est simple à énoncer : ne jamais calculer deux fois la même chose. Quand on a trouvé $F_3$, on le range quelque part ; la fois suivante, on le relit au lieu de le recalculer. C'est le cœur de l'idée naturelle sur laquelle reposent la programmation dynamique et la mémoïsation, deux techniques très proches ⁵.

Un problème se prête à la programmation dynamique quand deux conditions sont réunies : on peut le découper en sous-problèmes de même nature, et ces sous-problèmes se recoupent (on retombe sur les mêmes). Sans recoupement, le diviser pour régner suffit.

La première façon de procéder garde la fonction récursive, mais lui ajoute une mémoire. Avant de calculer, la fonction regarde si la réponse est déjà connue. Si oui, elle la renvoie. Sinon, elle la calcule, la range, puis la renvoie. On part du problème initial (le « haut ») et on descend vers les cas de base : c'est la méthode descendante.

La seconde façon renverse le point de vue. Au lieu de partir du haut et de descendre, on part des cas de base et on construit les sous-problèmes des plus petits aux plus grands, dans l'ordre, en remplissant un tableau ⁶. Il n'y a plus de récursivité : une simple boucle suffit. C'est la méthode ascendante.

Passons à un vrai problème d'optimisation. Tu disposes de pièces de valeurs données (par exemple 1, 3 et 4 centimes), en quantité illimitée. Il faut rendre une somme $S$ avec le plus petit nombre de pièces possible.

Le sac à dos (knapsack en anglais) est un grand classique de la recherche opérationnelle ⁶. On dispose de $n$ objets, chacun avec un poids $w_i$ et une valeur $c_i$ ⁴, et d'un sac qui supporte un poids maximal. On cherche à emporter des objets de valeur totale maximale sans dépasser cette capacité.

Plusieurs problèmes peuvent être abordés à l'aide de la programmation dynamique. Éduscol s'intéresse notamment à la recherche de la plus longue sous-chaîne commune de deux textes $x$ et $y$ ². Voici l'idée, construite avec nos propres outils.

D'autres usages existent : l'algorithme CYK, qui sert à l'analyse syntaxique, et la détection de ruptures, pour laquelle la programmation dynamique est la méthode la plus utilisée ⁶.