Structures de données - Programmation dynamique
L'approche de programmation dynamique est similaire à diviser pour vaincre en décomposant le problème en sous-problèmes possibles plus petits et plus petits. Mais contrairement à, diviser pour conquérir, ces sous-problèmes ne sont pas résolus indépendamment. Les résultats de ces sous-problèmes plus petits sont plutôt mémorisés et utilisés pour des sous-problèmes similaires ou qui se chevauchent.
La programmation dynamique est utilisée là où nous avons des problèmes, qui peuvent être divisés en sous-problèmes similaires, afin que leurs résultats puissent être réutilisés. La plupart du temps, ces algorithmes sont utilisés pour l'optimisation. Avant de résoudre le sous-problème en cours, l'algorithme dynamique essaiera d'examiner les résultats des sous-problèmes précédemment résolus. Les solutions des sous-problèmes sont combinées afin d'obtenir la meilleure solution.
Nous pouvons donc dire que -
Le problème devrait pouvoir être divisé en sous-problème plus petit qui se chevauchent.
Une solution optimale peut être obtenue en utilisant une solution optimale de sous-problèmes plus petits.
Les algorithmes dynamiques utilisent la mémorisation.
Comparaison
Contrairement aux algorithmes gourmands, où l'optimisation locale est abordée, les algorithmes dynamiques sont motivés pour une optimisation globale du problème.
Contrairement aux algorithmes de division et de conquête, où les solutions sont combinées pour parvenir à une solution globale, les algorithmes dynamiques utilisent la sortie d'un sous-problème plus petit, puis tentent d'optimiser un sous-problème plus grand. Les algorithmes dynamiques utilisent la mémorisation pour se souvenir de la sortie des sous-problèmes déjà résolus.
Exemple
Les problèmes informatiques suivants peuvent être résolus en utilisant une approche de programmation dynamique -
- Série de numéros de Fibonacci
- Problème de sac à dos
- La tour de Hanoi
- Chemin le plus court de toutes les paires par Floyd-Warshall
- Chemin le plus court par Dijkstra
- Planification du projet
La programmation dynamique peut être utilisée à la fois de manière descendante et ascendante. Et bien sûr, la plupart du temps, se référer à la sortie de la solution précédente est moins cher que recalculer en termes de cycles CPU.