Programmation dynamique : qu'est-ce que c'est, comment ça marche et ressources d'apprentissage
Publié: 2022-12-30La programmation dynamique est un concept développé par Richard Bellman, mathématicien et économiste.
À l'époque, Bellman cherchait un moyen de résoudre des problèmes d'optimisation complexes. Les problèmes d'optimisation vous obligent à choisir la meilleure solution parmi un ensemble d'options.
Un exemple de problème d'optimisation est le problème du voyageur de commerce. Le but est de trouver le chemin le plus court pour permettre au vendeur de visiter chaque ville exactement une fois et de revenir à la ville de départ.
L'approche de Bellman à ces problèmes était de les diviser en sous-problèmes plus petits et de résoudre les sous-problèmes du plus petit au plus grand. Il a ensuite stocké les résultats des sous-problèmes et les a réutilisés pour résoudre des sous-problèmes plus importants. C'est l'idée principale derrière la programmation dynamique.
Qu'est-ce que la programmation dynamique ?
La programmation dynamique résout les problèmes d'optimisation en les décomposant en sous-problèmes plus petits, en résolvant chaque sous-problème une fois et en stockant leurs solutions afin qu'elles puissent être réutilisées et combinées pour résoudre le problème plus vaste. Les problèmes sont résolus du plus petit au plus grand, ce qui permet de réutiliser les solutions.
Comment fonctionne la programmation dynamique ?
La résolution d'un problème à l'aide de la programmation dynamique implique les étapes suivantes :
- Définir les sous-problèmes : Un grand problème est divisé en petits sous-problèmes.
- Résoudre les sous-problèmes : Cela implique de résoudre le sous-problème identifié, ce qui peut être fait en utilisant la récursivité ou l'itération.
- Stocker les solutions : Les solutions aux sous-problèmes sont stockées afin de pouvoir être réutilisées.
- Construire la solution au problème original : La solution au grand problème est construite à partir des sous-problèmes qui ont déjà été calculés.
Pour voir cela en action, nous calculons le 6ème nombre de Fibonacci, F(6), en utilisant ce processus.
Tout d'abord, définissez les sous-problèmes à résoudre.
F(n) = F(n-1) + F(n-2) pour n > 1
Donc : 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 à l'aide d'une fonction récursive ou d'un processus itératif. Nous résolvons les sous-problèmes du plus petit au plus grand, en réutilisant les résultats de sous-problèmes plus petits. Cela nous donne ceci :
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 que nous résolvons chacun des sous-problèmes, nous stockons les solutions dans un tableau ou une table afin qu'elles puissent être réutilisées pour résoudre des sous-problèmes plus importants comme ceci :
| n | F(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
Une fois que tous les sous-problèmes ont été résolus, nous utilisons les solutions pour construire la solution au problème initial.
Dans ce cas, la solution au problème original est le 6ème nombre de Fibonacci, qui est trouvé en additionnant les résultats de F(5) et F(4), sous-problèmes identifiés à partir du plus grand problème. Le résultat nous donne 8.
Où et pourquoi la programmation dynamique est-elle utilisée ?
La programmation dynamique est utilisée dans les domaines où nous avons des problèmes qui peuvent être divisés en sous-problèmes plus petits, et leurs solutions sont utilisées pour résoudre des problèmes plus importants.
Ces domaines comprennent l'informatique, l'économie, les mathématiques et l'ingénierie. En informatique, il est utilisé pour résoudre des problèmes impliquant des séquences, des graphiques et des valeurs entières et dans la programmation compétitive.
En économie, il est utilisé pour résoudre des problèmes d'optimisation dans les finances, la production et l'allocation des ressources. En mathématiques, la programmation dynamique est utilisée dans la théorie des jeux, les statistiques et les probabilités, où elle est utilisée pour résoudre des problèmes d'optimisation.
En ingénierie, il est utilisé pour résoudre des problèmes d'allocation des ressources, de planification, de fabrication, de communication et de systèmes de contrôle.
Il y a plusieurs avantages à utiliser la programmation dynamique pour résoudre des problèmes d'optimisation :
- Efficacité : La programmation dynamique peut être plus efficace que d'autres algorithmes d'optimisation car elle évite le recalcul de problèmes similaires plusieurs fois.
- Résolution de grands problèmes : la programmation dynamique est idéale pour les grands problèmes d'optimisation qu'il serait impossible de résoudre à l'aide d'autres méthodes. En effet, il divise le problème en problèmes plus petits, ce qui réduit leur complexité.
- Solutions optimales : Les algorithmes de programmation dynamique peuvent trouver la solution optimale à un problème si les sous-problèmes et les objectifs sont correctement définis.
- Simplicité : Les algorithmes de programmation dynamique sont simples à mettre en œuvre et à comprendre, surtout si le problème peut être défini dans un ordre spécifique.
- Extensibilité : les algorithmes de programmation dynamique peuvent être facilement étendus pour résoudre des problèmes plus complexes en ajoutant des sous-problèmes supplémentaires et en modifiant les objectifs du problème.
Lorsqu'il s'agit de résoudre des problèmes d'optimisation, la programmation dynamique est un outil très utile pour assurer l'efficacité des solutions.
Approches utilisées dans la programmation dynamique
En programmation dynamique, deux approches sont utilisées pour résoudre des problèmes d'optimisation. Il s'agit de l'approche descendante et de l'approche ascendante.
Approche descendante
Cette approche est également connue sous le nom de mémorisation. La mémorisation est une technique d'optimisation principalement utilisée pour accélérer les programmes informatiques en stockant les résultats des appels de fonction dans le cache et en renvoyant les résultats mis en cache la prochaine fois qu'ils sont nécessaires plutôt que de les recalculer.
L'approche descendante implique la récursivité et la mise en cache. La récursivité implique une fonction s'appelant elle-même avec des versions plus simples du problème comme argument. La récursivité est utilisée pour décomposer le problème en sous-problèmes plus petits et résoudre les sous-problèmes.
Une fois qu'un sous-problème est résolu, son résultat est mis en cache et réutilisé chaque fois qu'un problème similaire survient. Le top-down est facile à comprendre et à mettre en œuvre et ne résout un sous-problème qu'une seule fois. Un inconvénient, cependant, est qu'il prend beaucoup de mémoire à cause de la récursivité. Cela peut entraîner une erreur de débordement de pile.
Une approche en profondeur
L'approche ascendante, également connue sous le nom de tabulation, supprime la récursivité en la remplaçant par l'itération, évitant ainsi les erreurs de débordement de pile.
Dans cette approche, un grand problème est divisé en sous-problèmes plus petits, et les solutions des sous-problèmes sont utilisées pour résoudre le problème plus grand.
Les sous-problèmes plus petits sont d'abord résolus du plus grand au plus petit, et leurs résultats sont stockés dans une matrice, un tableau ou un tableau, d'où le nom de tabulation.
Les résultats stockés résolvent des problèmes plus importants qui dépendent des sous-problèmes. Le résultat du problème original est ensuite trouvé en résolvant le plus grand sous-problème en utilisant les valeurs calculées précédemment.
Cette approche a l'avantage d'être économe en mémoire et en temps en supprimant la récursivité.
Exemples de problèmes pouvant être résolus par la programmation dynamique
Voici quelques problèmes de programmation qui peuvent être résolus à l'aide de la programmation dynamique :
#1. Problème de sac à dos
Un sac à dos est un sac en toile, en nylon ou en cuir généralement attaché à l'arrière et utilisé par les soldats et les randonneurs pour transporter des fournitures.
Dans le problème du sac à dos, on vous présente un sac à dos, et compte tenu de sa capacité de charge, vous devez choisir des objets, chacun avec sa valeur. Votre sélection doit être telle que vous obteniez la valeur totale maximale des articles sélectionnés et que le poids des articles soit inférieur ou égal à la capacité du sac à dos.
Un exemple du problème du sac à dos est donné ci-dessous :
Imaginez que vous partez en randonnée et que vous avez un sac à dos d'une capacité de 15 kilogrammes. Vous avez une liste d'articles que vous pouvez apporter avec vous, ainsi que leurs valeurs et poids, comme indiqué dans le tableau ci-dessous :
| Article | Évaluer | Poids |
|---|---|---|
| Tente | 200 | 3 |
| Sac de couchage | 150 | 2 |
| Poêle | 50 | 1 |
| Aliments | 100 | 2 |
| Bouteille d'eau | dix | 0,5 |
| Trousse de premiers secours | 25 | 1 |
Choisissez un sous-ensemble d'articles à apporter de sorte que la valeur totale des articles soit maximisée tandis que le poids total est inférieur ou égal à la capacité du sac à dos, qui est de 15 kilogrammes.
Les applications réelles du problème du sac à dos impliquent de sélectionner des titres à ajouter à un portefeuille afin de minimiser les risques et de maximiser les profits et de trouver les moyens les moins coûteux de réduire les matières premières.
#2. Problème de planification
Un problème d'ordonnancement est un problème d'optimisation dans lequel le but est d'affecter de manière optimale des tâches à un ensemble de ressources. Les ressources peuvent être des machines, du personnel ou d'autres ressources utilisées pour accomplir les tâches.
Un exemple de problème d'ordonnancement est donné ci-dessous :
Imaginez que vous êtes un chef de projet responsable de la planification d'un ensemble de tâches qui doivent être réalisées par une équipe d'employés. Chaque tâche a une heure de début, une heure de fin et une liste d'employés qualifiés pour l'accomplir.
Voici un tableau qui décrit 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 | dix | 12 | A, C |
| T3 | 11 | 13 | AVANT JC |
| T4 | 12 | 14 | UN B |
Attribuez chaque tâche à un employé pour minimiser le temps d'exécution total.
Le problème d'ordonnancement peut être rencontré dans l'industrie manufacturière lorsque l'on tente d'optimiser l'allocation des ressources telles que les machines, les matériaux, les outils et la main-d'œuvre.
Il peut également être rencontré dans les soins de santé lors de l'optimisation de l'utilisation des lits, du personnel et des fournitures médicales. D'autres industries 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 de voyageur de commerce
C'est l'un des problèmes d'optimisation les plus étudiés qui peuvent être résolus à l'aide de la programmation dynamique.
Le problème du voyageur de commerce fournit une liste de villes et les distances entre chaque paire de villes. Vous devez trouver l'itinéraire le plus court possible qui visite chaque ville exactement une fois et retourne à la ville d'origine.
Un exemple de problème de voyageur de commerce est donné ci-dessous :
Imaginez que vous êtes un vendeur qui a besoin de visiter un ensemble de villes dans les plus brefs délais. Vous avez une liste des villes que vous devez visiter et les distances entre chaque paire de villes, comme indiqué dans le tableau ci-dessous :
| Ville | UNE | B | C | ré | E |
|---|---|---|---|---|---|
| UNE | 0 | dix | 15 | 20 | 30 |
| B | dix | 0 | 35 | 25 | 15 |
| C | 15 | 35 | 0 | 30 | 20 |
| ré | 20 | 25 | 30 | 0 | dix |
| E | 30 | 15 | 20 | dix | 0 |
Le problème du voyageur de commerce peut être rencontré dans l'industrie des loisirs lors de la planification d'itinéraires pour les touristes, la logistique lors de la planification de l'expédition de marchandises, le transport lors de la planification des itinéraires de bus et dans l'industrie de la vente, entre autres.
De toute évidence, la programmation dynamique a de nombreuses applications dans le monde réel, ce qui permet d'en apprendre davantage à son sujet.
Considérez les ressources suivantes pour approfondir vos connaissances en programmation dynamique.
Ressources
Programmation dynamique par Richard Bellman
La programmation dynamique est un livre de Richard Bellman, qui a proposé la programmation dynamique et l'a développée à ses débuts.
| Aperçu | Produit | Notation | Prix | |
|---|---|---|---|---|
 | Programmation dynamique (Dover Books on Computer Science) | 17,29 $ | Acheter sur Amazon |
Le livre est écrit d'une manière facile à comprendre qui ne nécessite que des connaissances de base en mathématiques et en calcul pour comprendre le texte. Dans le livre, Bellman présente la théorie mathématique d'un processus de décision en plusieurs étapes qui est la clé de la programmation dynamique.
Le livre examine ensuite les problèmes de goulot d'étranglement dans les processus de production à plusieurs étapes, les théorèmes d'existence et d'unicité et l'équation d'inventaire optimale.
La meilleure chose à propos du livre est que Bellman offre des exemples de nombreux problèmes complexes 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 et montre comment la programmation dynamique peut résoudre les problèmes.
Le livre est disponible en versions Kindle, couverture rigide et livre de poche.
Cours de master sur les algorithmes de programmation dynamique
Ce cours de maîtrise sur les algorithmes de programmation dynamique d'Udemy est proposé par Apaar Kamal, ingénieur logiciel chez Google, et Prateek Narang, qui a également travaillé avec Google.
Le cours est optimisé pour aider les apprenants à exceller dans les compétitions de programmation qui comportent de nombreux problèmes nécessitant une programmation dynamique.
Outre les concurrents de programmation, le cours est idéal pour les programmeurs qui cherchent à améliorer leur compréhension des algorithmes et les personnes qui se préparent à des entretiens de programmation et à des cycles de codage en ligne.
Le cours, qui dure plus de 40 heures, couvre en profondeur la programmation dynamique. Le cours offre d'abord un rappel sur des concepts tels que la récursivité et le retour en arrière.
Il couvre ensuite la programmation dynamique dans la théorie des jeux, les chaînes, les arbres et les graphiques, l'exponentiation matricielle, les masques de bits, la combinatoire et les sous-séquences, les problèmes de partition et la programmation dynamique multidimensionnelle, parmi de nombreux autres concepts.
Essentiels de la programmation compétitive, algorithmes maîtres
Udemy propose un cours 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 et algorithmes avancés d'une manière utile et pertinente pour les programmeurs compétitifs.
Le cours offre un rappel sur les structures de données et les algorithmes avant de plonger dans des algorithmes et des techniques plus complexes qui sont utiles dans la programmation compétitive.
Le cours couvre la programmation dynamique, les mathématiques, la théorie des jeux, la correspondance de modèles, le masquage de bits et une myriade d'algorithmes avancés utilisés et testés lors de compétitions de programmation.
Le cours Udemy est divisé en 10 modules et 42 sections et propose de nombreuses questions pratiques après chaque section. Ce cours best-seller est un incontournable pour quiconque s'intéresse à la programmation compétitive.
Derniers mots
La programmation dynamique est une compétence bénéfique pour tout programmeur à apprendre à améliorer sa résolution de problèmes de problèmes du monde réel. Par conséquent, les programmeurs devraient envisager de parcourir les ressources suggérées pour ajouter cet outil crucial à leur boîte à outils.
Ensuite, vous pouvez découvrir les langages de programmation à utiliser en science des données.