programmation dynamique

Dans un système monétaire fictif, on veut former 6 centimes avec des pièces de 1, 3 et 4 centimes. Plusieurs essais réutilisent les mêmes petits montants : chercher 6 oblige à connaître les meilleures solutions pour 5, 3 et 2.

La programmation dynamique enregistre la meilleure réponse obtenue pour chaque montant, puis s'en sert pour construire les suivants. Ainsi, un sous-problème n'est résolu qu'une fois. Pour 6 centimes, elle trouve deux pièces de 3 centimes, alors qu'un choix immédiat de 4 centimes conduirait à trois pièces.

La programmation dynamique, appelée dynamic programming en anglais, est une méthode algorithmique qui remplace un problème par une famille de sous-problèmes et conserve leurs résultats afin de ne pas refaire les mêmes calculs. Elle permet notamment de résoudre des problèmes d'optimisation, mais aussi de comptage ou de décision. Pour un problème d'optimisation, elle est adaptée lorsque plusieurs branches rencontrent les mêmes sous-problèmes et lorsque la solution optimale se construit à partir de solutions optimales plus petites. Cette seconde propriété est le principe d'optimalité de Bellman, associé à Richard Bellman.

Deux organisations sont courantes. Avec la mémoïsation, le calcul part du problème demandé, descend récursivement vers les sous-problèmes nécessaires et met chaque réponse en cache. Avec la tabulation, il part de cas de base et remplit une table dans un ordre où les dépendances sont déjà connues. Dans les deux cas, l'état doit contenir toute l'information nécessaire à la suite du calcul, et une relation de récurrence relie chaque état à des états plus simples.

La méthode intervient notamment dans la suite de Fibonacci, le problème du sac à dos, le rendu de monnaie et les problèmes de plus court chemin étudiés en recherche opérationnelle. Bellman-Ford procède par relaxations répétées compatibles avec cette famille d'idées. Dijkstra résout aussi un problème de plus court chemin, mais son choix du sommet courant relève d'une stratégie gloutonne : tout algorithme cité dans le même domaine n'est donc pas nécessairement un algorithme de programmation dynamique.

Dans un système monétaire fictif, on veut former exactement 6 centimes avec un minimum de pièces de 1, 3 et 4 centimes, disponibles sans limite. Pour tout entier s de 0 à 6, C(s) désigne ce minimum ; C(0) = 0.

1. Pour un montant s positif, on essaie chaque coupure d qui ne dépasse pas s. On ajoute une pièce à la meilleure solution pour s − d :

2. À partir de C(0), la table donne C(1) = 1, C(2) = 2, C(3) = 1 et C(4) = 1.

3. Pour 5 centimes, les prédécesseurs 4, 2 et 1 coûtent 1, 2 et 1 pièce. Ainsi, C(5) = 2.

4. Pour 6 centimes, les prédécesseurs 5, 3 et 2 coûtent 2, 1 et 2 pièces. Le minimum donne C(6) = 2, avec 3 + 3.

Le résultat est exactement deux pièces pour 6 centimes ; l'égalité 3 + 3 = 6 fournit un contrôle direct. Le choix glouton de la plus grande pièce aurait produit 4 + 1 + 1, soit trois pièces. La table des sept états rend visible le chemin optimal 0, 3, 6.

Dans un problème de rendu de monnaie ou de sac à dos, on commence par préciser l'état, le choix possible et la valeur à optimiser. Si les mêmes états reviennent et si une solution optimale se compose de solutions optimales plus petites, une table évite les recalculs.

Quand seuls quelques états sont réellement visités, la mémoïsation calcule à la demande. Quand un ordre simple permet d'énumérer tous les états utiles, la tabulation rend les dépendances et le point d'arrêt explicites.

Pour un plus court chemin, il faut d'abord examiner la structure du problème et les hypothèses de l'algorithme choisi. Bellman-Ford et Dijkstra ne suivent pas le même mécanisme ; le fait qu'ils visent tous deux une distance minimale ne suffit pas à les classer de la même façon.

Une stratégie gloutonne reste préférable lorsqu'un choix local peut être prouvé toujours optimal, car elle n'a pas besoin d'explorer toute une famille d'états. Les pièces de 1, 3 et 4 centimes montrent le critère contraire : à 6 centimes, prendre d'abord 4 échoue.

Programmation dynamique et stratégie gloutonne. La première construit la réponse à partir d’états reliés par une récurrence et réutilise les sous-résultats mémorisés ; la seconde fige un choix local sans revenir dessus. Dans cet exemple d’optimisation, avec les pièces de 1, 3 et 4 centimes, le montant de 6 sépare les deux démarches : 3 + 3 utilise deux pièces, contre 4 + 1 + 1 pour le choix glouton.

Programmation dynamique et diviser pour régner. Les deux méthodes décomposent un problème. Le critère distinctif est le recouvrement : la programmation dynamique réutilise la réponse à un même sous-problème, tandis qu'une décomposition en sous-problèmes indépendants n'exige pas cette mémoire partagée.

Programmation dynamique et mémoïsation. La mémoïsation est une technique de cache, pas le nom de tout problème dynamique. Mettre en cache une fonction évite des appels répétés ; il n'y a programmation dynamique que si les états et leur relation construisent la réponse au problème considéré.

État incomplet. Si deux situations enregistrées sous le même état peuvent avoir des suites différentes, la table fusionne à tort des cas distincts. Le symptôme est une récurrence qui réclame une information absente ; il faut alors enrichir l'état avant de calculer.

Optimalité non décomposable. Un meilleur choix global ne provient pas toujours de meilleurs choix locaux pour les sous-problèmes retenus. Si remplacer une sous-solution par une meilleure peut détériorer le résultat final, le principe d'optimalité ne s'applique pas à cette décomposition ; il faut changer d'état ou de méthode.

Recouvrement faible. Lorsque chaque sous-problème n'apparaît qu'une fois, mémoriser toutes les réponses n'évite aucun recalcul. Une décomposition directe suffit alors et économise la table. À l'autre extrême, un espace d'états trop vaste peut rendre le temps ou la mémoire nécessaires impraticables.

Ordre de calcul invalide. Une tabulation ne peut utiliser une valeur qui n'a pas encore été établie. Le cas charnière est le montant 0 dans l'exemple : C(0) = 0 doit être posé avant C(1), puis les montants doivent être traités dans l'ordre croissant. En présence de dépendances cycliques, une simple passe ne suffit pas.

algorithme — Situer données, instructions, résultat et condition d'arrêt dans le cadre général d'une procédure de calcul.

suite de Fibonacci — Observer un exemple classique où les mêmes termes antérieurs réapparaissent dans le calcul.

algorithme de Bellman-Ford — Approfondir un calcul de plus court chemin fondé sur des relaxations répétées.

recherche opérationnelle — Replacer l'optimisation et la décision parmi les domaines d'application de la méthode.