La programmation dynamique, une approche de résolution de problèmes, a été conceptualisée par Richard Bellman, un éminent mathématicien et économiste.
Bellman, à son époque, s’intéressait à une méthodologie pour aborder les défis d’optimisation complexes. Ces problèmes exigent de sélectionner la meilleure option parmi plusieurs alternatives possibles.
Le problème du voyageur de commerce illustre bien cette notion d’optimisation. L’objectif est de trouver l’itinéraire le plus court qui permettrait à un voyageur de visiter chaque ville une seule fois, pour ensuite revenir à son point de départ.
La méthode de Bellman consistait à décomposer ces problèmes en sous-problèmes plus simples, puis à les résoudre par ordre de complexité croissante. Les solutions de ces sous-problèmes étaient ensuite stockées et réutilisées pour résoudre des problèmes de plus grande envergure. C’est l’essence même de la programmation dynamique.
Qu’est-ce que la programmation dynamique ?
La programmation dynamique est une technique qui s’attaque aux problèmes d’optimisation en les divisant en sous-problèmes. Chaque sous-problème est résolu une seule fois, et sa solution est enregistrée afin d’être réutilisée et combinée avec d’autres solutions pour résoudre le problème initial. Cette approche procède du plus petit au plus grand problème, en maximisant la réutilisation des solutions.
Comment fonctionne la programmation dynamique ?
La mise en œuvre de la programmation dynamique pour résoudre un problème implique plusieurs étapes :
- Identification des sous-problèmes : le problème principal est segmenté en sous-problèmes plus simples.
- Résolution des sous-problèmes : chaque sous-problème identifié est résolu, soit par récursivité, soit par itération.
- Stockage des solutions : les résultats des sous-problèmes sont mémorisés pour une réutilisation ultérieure.
- Construction de la solution finale : la solution au problème original est assemblée à partir des solutions des sous-problèmes déjà calculés.
Pour illustrer ce processus, calculons le 6ème nombre de Fibonacci, F(6), en appliquant cette méthode.
D’abord, définissons les sous-problèmes à résoudre.
F(n) = F(n-1) + F(n-2) pour n > 1
Par conséquent : F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
La deuxième étape consiste à résoudre chaque sous-problème, en utilisant une fonction récursive ou une approche itérative. On résout les sous-problèmes du plus simple au plus complexe, en exploitant les résultats des sous-problèmes déjà calculés. Cela donne :
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Au fur et à mesure de la résolution de chaque sous-problème, on stocke les résultats dans un tableau ou une table pour permettre leur réutilisation lors de la résolution de sous-problèmes de plus grande envergure.
Une fois tous les sous-problèmes résolus, on utilise ces solutions pour construire la solution au problème original.
Dans cet exemple, la solution est le 6ème nombre de Fibonacci, obtenu en additionnant les résultats de F(5) et F(4), qui sont les sous-problèmes identifiés dans le problème initial. Le résultat est 8.
Domaines d’application de la programmation dynamique et raisons de son utilisation
La programmation dynamique est un outil pertinent lorsque l’on est confronté à des problèmes qui peuvent être décomposés en sous-problèmes, et dont les solutions peuvent être exploitées pour résoudre des problèmes plus complexes.
On retrouve cette technique dans des domaines variés tels que l’informatique, l’économie, les mathématiques et l’ingénierie. En informatique, elle est utilisée pour résoudre des problèmes liés aux séquences, aux graphes, aux nombres entiers et dans la programmation compétitive.
En économie, elle permet de résoudre des problèmes d’optimisation en finance, dans la production et l’allocation de ressources. En mathématiques, la programmation dynamique est employée dans la théorie des jeux, les statistiques et les probabilités pour résoudre des problèmes d’optimisation.
En ingénierie, elle trouve son application dans la répartition des ressources, la planification, la fabrication, les communications et les systèmes de contrôle.
L’utilisation de la programmation dynamique pour la résolution de problèmes d’optimisation présente plusieurs avantages :
- Efficacité : la programmation dynamique peut être plus efficace que d’autres algorithmes d’optimisation car elle évite de recalculer plusieurs fois les mêmes sous-problèmes.
- Résolution de problèmes complexes : elle est particulièrement adaptée aux problèmes d’optimisation de grande envergure qui seraient impossibles à résoudre avec d’autres méthodes, en raison de la division du problème initial en éléments plus simples.
- Solutions optimales : les algorithmes de programmation dynamique peuvent déterminer la solution optimale d’un problème si les sous-problèmes et les objectifs sont bien définis.
- Simplicité : Les algorithmes de programmation dynamique sont relativement simples à implémenter et à comprendre, surtout si le problème peut être structuré de manière séquentielle.
- Extensibilité : Les algorithmes de programmation dynamique peuvent être aisément étendus pour résoudre des problèmes plus complexes en ajoutant des sous-problèmes ou en modifiant les objectifs du problème.
La programmation dynamique se révèle ainsi un outil très efficace pour aborder les problèmes d’optimisation et garantir l’efficience des solutions.
Approches utilisées en programmation dynamique
La programmation dynamique utilise deux approches principales pour résoudre les problèmes d’optimisation : l’approche descendante et l’approche ascendante.
Approche descendante
Cette approche est également connue sous le nom de mémoïsation. La mémoïsation est une technique d’optimisation qui vise à accélérer les programmes en stockant les résultats des appels de fonction dans un cache et en renvoyant ces résultats mis en cache lors d’appels ultérieurs au lieu de recalculer ces valeurs.
L’approche descendante repose sur la récursivité et la mise en cache. La récursivité implique qu’une fonction s’appelle elle-même, en utilisant des versions plus simples du problème comme arguments. La récursivité sert à décomposer un problème en sous-problèmes plus simples et à résoudre ces derniers.
Une fois un sous-problème résolu, son résultat est mis en cache et réutilisé à chaque fois qu’un problème similaire se présente. L’approche descendante est facile à appréhender et à mettre en œuvre, et un sous-problème n’est résolu qu’une seule fois. Cependant, elle requiert une quantité de mémoire importante en raison de la récursivité, ce qui peut mener à une erreur de dépassement de pile.
Approche ascendante
L’approche ascendante, aussi appelée tabulation, élimine la récursivité en la remplaçant par une itération, évitant ainsi les erreurs de dépassement de pile.
Dans cette approche, le problème principal est divisé en sous-problèmes plus petits, et les solutions de ces sous-problèmes servent à résoudre le problème principal.
Les sous-problèmes sont résolus par ordre de taille croissante, et leurs résultats sont stockés dans une matrice, un tableau ou une table, d’où le terme de « tabulation ».
Les résultats stockés servent à résoudre des problèmes plus complexes qui dépendent de ces sous-problèmes. La solution du problème initial est trouvée en résolvant le plus grand sous-problème en utilisant les valeurs calculées précédemment.
Cette approche présente l’avantage d’être plus économe en mémoire et en temps, en éliminant la récursivité.
Exemples de problèmes résolvables par programmation dynamique
Voici quelques exemples de problèmes qui peuvent être résolus à l’aide de la programmation dynamique :
#1. Problème du sac à dos
Source : Wikipédia
Un sac à dos est un sac en toile, en nylon ou en cuir, généralement porté sur le dos et utilisé pour transporter des fournitures.
Dans le problème du sac à dos, vous devez choisir des objets, chacun ayant une valeur et un poids, en respectant la capacité maximale du sac. Le but est de maximiser la valeur totale des objets sélectionnés sans dépasser la capacité du sac.
Voici un exemple de problème de sac à dos :
Imaginez que vous partez en randonnée et que vous avez un sac à dos d’une capacité de 15 kilogrammes. Vous disposez d’une liste d’articles, avec leurs valeurs et poids :
| Article | Valeur | Poids |
| Tente | 200 | 3 |
| Sac de couchage | 150 | 2 |
| Réchaud | 50 | 1 |
| Nourriture | 100 | 2 |
| Bouteille d’eau | 100 | 0.5 |
| Trousse de secours | 25 | 1 |
Sélectionnez un sous-ensemble d’articles à emporter, de manière à ce que leur valeur totale soit maximale tout en respectant la capacité du sac à dos, soit 15 kilogrammes.
Les applications réelles du problème du sac à dos consistent par exemple à sélectionner les titres à ajouter à un portefeuille pour minimiser les risques et maximiser les profits, ou à trouver la manière la moins coûteuse de réduire les matières premières.
#2. Problème de planification
Un problème de planification est un problème d’optimisation où l’objectif est d’attribuer des tâches à un ensemble de ressources de manière optimale. Ces ressources peuvent être des machines, du personnel ou d’autres éléments nécessaires à la réalisation des tâches.
Voici un exemple de problème de planification :
Imaginez que vous êtes chef de projet et que vous devez planifier un ensemble de tâches à réaliser par une équipe. Chaque tâche a une heure de début, une heure de fin et une liste d’employés qualifiés pour l’exécuter.
Voici un tableau décrivant les tâches et leurs caractéristiques :
| Tâche | Heure de début | Heure de fin | Employés qualifiés |
| T1 | 9 | 11 | A, B, C |
| T2 | 10 | 12 | A, C |
| T3 | 11 | 13 | B, C |
| T4 | 12 | 14 | A, B |
Attribuez chaque tâche à un employé de manière à minimiser le temps d’exécution total.
Le problème de planification est fréquemment rencontré dans l’industrie manufacturière où l’on cherche à optimiser l’allocation des ressources telles que les machines, les matériaux, les outils et la main-d’œuvre.
Il se pose également dans le secteur de la santé pour optimiser l’utilisation des lits, du personnel et des fournitures médicales. D’autres secteurs où ce problème peut survenir sont la gestion de projet, la gestion de la chaîne d’approvisionnement et l’éducation.
#3. Problème du voyageur de commerce
Source : Wikipédia
C’est l’un des problèmes d’optimisation les plus étudiés qui peut être résolu à l’aide de la programmation dynamique.
Le problème du voyageur de commerce consiste à trouver le chemin le plus court qui permet de visiter une liste de villes, en ne passant qu’une seule fois par chaque ville, et en revenant à la ville de départ.
Voici un exemple du problème du voyageur de commerce :
Imaginez que vous êtes un vendeur qui doit visiter un ensemble de villes le plus rapidement possible. Vous avez une liste des villes que vous devez visiter et les distances entre chaque paire de villes :
| Ville | A | B | C | D | E |
| A | 0 | 10 | 15 | 20 | 30 |
| B | 10 | 0 | 35 | 25 | 15 |
| C | 15 | 35 | 0 | 30 | 20 |
| D | 20 | 25 | 30 | 0 | 10 |
| E | 30 | 15 | 20 | 10 | 0 |
Le problème du voyageur de commerce est souvent rencontré dans l’industrie du tourisme lors de la planification d’itinéraires pour les touristes, dans la logistique pour l’expédition de marchandises, dans le transport pour l’organisation de tournées de bus et dans le secteur de la vente.
La programmation dynamique trouve donc de nombreuses applications concrètes, ce qui justifie l’importance de son apprentissage.
Voici quelques ressources pour approfondir vos connaissances en programmation dynamique.
Ressources
Programmation dynamique par Richard Bellman
La programmation dynamique est un livre de Richard Bellman, le concepteur de cette approche.
Ce livre présente les concepts de manière accessible, avec seulement des connaissances de base en mathématiques et en calcul. Bellman y expose la théorie mathématique d’un processus de décision en plusieurs étapes, qui est au cœur de la programmation dynamique.
Le livre aborde également les problèmes de goulot d’étranglement dans les processus de production en plusieurs étapes, les théorèmes d’existence et d’unicité ainsi que l’équation d’inventaire optimale.
Bellman illustre la théorie par de nombreux exemples concrets, dans des domaines tels que la logistique, la théorie de l’ordonnancement, la théorie de la communication, l’économie mathématique et les processus de contrôle, démontrant ainsi l’utilité de la programmation dynamique pour résoudre des problèmes complexes.
Le livre est disponible en version Kindle, reliée et brochée.
Cours de master sur les algorithmes de programmation dynamique
Ce cours de maîtrise sur les algorithmes de programmation dynamique proposé sur Udemy est animé par Apaar Kamal, ingénieur logiciel chez Google, et Prateek Narang, qui a également travaillé chez Google.
Ce cours est conçu pour aider les participants à exceller dans les compétitions de programmation qui comportent de nombreux problèmes nécessitant des compétences en programmation dynamique.
Ce cours s’adresse également aux programmeurs qui cherchent à améliorer leur compréhension des algorithmes, ainsi qu’aux personnes qui préparent des entretiens d’embauche et des tests de programmation en ligne.
Ce cours de plus de 40 heures offre une formation approfondie en programmation dynamique. Il commence par des rappels sur des concepts tels que la récursivité et le retour en arrière.
Il aborde ensuite la programmation dynamique appliquée à la théorie des jeux, aux chaînes de caractères, aux arbres et aux graphes, à l’exponentiation matricielle, aux masques binaires, à la combinatoire, aux sous-séquences, aux problèmes de partition et à la programmation dynamique multidimensionnelle, entre autres.
Essentiels de la programmation compétitive, algorithmes maîtres
Udemy propose également un cours intitulé « Competitive Programming Essentials » par Prateek Narang et Amal Kamaar, qui couvre la programmation dynamique, les mathématiques, la théorie des nombres et les structures de données avancées, avec une approche axée sur les besoins des programmeurs compétitifs.
Ce cours commence par des rappels sur les structures de données et les algorithmes avant d’aborder des algorithmes et des techniques plus avancés et utiles dans la programmation compétitive.
Le contenu couvre la programmation dynamique, les mathématiques, la théorie des jeux, la correspondance de motifs, le masquage de bits, ainsi que divers algorithmes avancés couramment utilisés et évalués lors de compétitions de programmation.
Le cours Udemy est structuré en 10 modules et 42 sections, avec de nombreux exercices pratiques après chaque section. Ce cours, très populaire, est un atout majeur pour tous ceux qui s’intéressent à la programmation compétitive.
En conclusion
La programmation dynamique est une compétence très utile pour tout programmeur qui souhaite améliorer ses capacités de résolution de problèmes concrets. Il est donc recommandé d’explorer les ressources mentionnées afin d’enrichir sa boîte à outils.
Ensuite, vous pouvez explorer les langages de programmation à utiliser en science des données.