Qu'est-ce que la programmation dynamique?

La programmation dynamique, lorsqu'elle fait 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 décomposant le problème 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 des sous-problèmes ou des sous-structures optimales.Pour comprendre comment fonctionne la programmation dynamique, il est préférable de comprendre le concept derrière ces deux termes.

Les sous-problèmes qui se chevauchent décrivent des équations compliquées qui, lorsqu'elles sont décomposées en petits ensembles d'équations, réutilisez des parties des équations plus petites plus d'une fois pour atteindre une réponse.Par exemple, une équation mathématique qui a été invité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 d'autres résultats une seule fois.La programmation dynamique indiquerait à ce problème qu'après avoir calculé le résultat la première fois, il devrait enregistrer ce résultat et brancher la réponse sur l'équation plus tard au lieu de le calculer à nouveau.Lorsque vous traitez avec de longs processus et équations complexes, cela permet de 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 et en créant ensuite 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 pour chaque problème.Il calcule la réponse au problème d'origine des réponses plus petites.Les défauts existent avec ce processus.Bien qu'il donne la solution qui fonctionne le meilleur mathématiquement, il peut être la meilleure solution dans la vie réelle, selon le type de problème et la façon dont il se rapporte au monde réel.

Au cours de l'une de ces opérations, la programmation dynamiqueL'algorithme essaie de trouver le chemin le plus court vers la solution.Cela peut prendre l'une des deux approches pour ce faire.L'approche descendante décompose l'équation en équations plus petites et réutilise les réponses de ces équations si nécessaire.L'approche ascendante essaie de résoudre la plus petite valeur mathématique après avoir décomposé l'équation, puis se dirige vers le plus grand à partir de là.Les deux approches gagnent du temps, mais la programmation dynamique ne fonctionne que lorsque le problème d'origine peut se décomposer en équations plus petites qui, à un moment donné, sont réutilisées pour résoudre l'équation.