Qu'est-ce que la programmation dynamique?
La programmation dynamique, en référence au domaine de l'informatique, décrit un groupe d'algorithmes informatiques similaires destinés à résoudre des problèmes complexes en les décomposant en ensembles de problèmes plus petits. Créée pour la première fois par Richard Bellman dans les années 1950, la programmation dynamique fonctionne avec des problèmes qui se chevauchent soit des sous-problèmes soit des sous-structures optimales. Pour comprendre le fonctionnement de la programmation dynamique, il est préférable de comprendre le concept sous-jacent à ces deux termes.
Les sous-problèmes qui se chevauchent décrivent des équations complexes qui, lorsqu'elles sont décomposées en ensembles d'équations plus petits, réutilisent plusieurs fois des parties des équations plus petites pour obtenir une réponse. Par exemple, une équation mathématique censée calculer tous les résultats possibles à l'aide d'un ensemble de nombres peut calculer le même résultat plusieurs fois tout en calculant les autres résultats une seule fois. La programmation dynamique indiquerait à ce problème qu’après le calcul du résultat la première fois, il devrait enregistrer ce résultat et intégrer la réponse dans l’équation ultérieurement au lieu de la calculer à nouveau. Lorsque vous traitez avec des processus et des équations complexes et longs, cela vous fait gagner du temps et crée une solution plus rapide en utilisant beaucoup moins d'étapes.
Les sous-structures optimales créent une solution en trouvant la meilleure réponse à tous les sous-problèmes, puis en créant la meilleure réponse globale. Après avoir décomposé un problème complexe en problèmes plus petits, l’ordinateur utilise ensuite un système mathématique pour déterminer quelle est la meilleure réponse à chaque problème. Il calcule la réponse au problème initial à partir des réponses plus petites. Des failles existent avec ce processus. Bien que cela donne la solution qui fonctionne le mieux sur le plan mathématique, cela peut être ou ne pas être la meilleure solution dans la vie réelle, en fonction du type de problème et de son rapport avec le monde réel.
Au cours de l’une de ces opérations, l’algorithme de programmation dynamique essaie de trouver le chemin le plus court vers la solution. Pour ce faire, l’une des deux approches possibles peut être utilisée. L'approche descendante divise l'équation en équations plus petites et réutilise les réponses pour ces équations lorsque cela est nécessaire. L’approche ascendante essaie de résoudre la plus petite valeur mathématique après avoir décomposé l’équation, puis progresse vers la plus grande. Les deux approches permettent de gagner du temps, mais la programmation dynamique ne fonctionne que lorsque le problème initial peut se décomposer en équations plus petites qui, à un moment donné, sont réutilisées pour résoudre l'équation.