Définition
Programmation dynamique (DP)
Une approche algorithmique qui transforme des problèmes complexes en sous-problèmes plus simples et résout chaque sous-problème une seule fois.
Tableau de mémoïsation
Une structure de données utilisée pour stocker les résultats des sous-problèmes déjà résolus afin d'éviter des calculs répétitifs.
Sous-structure optimale
Un principe clé en programmation dynamique où une solution optimale réside à chaque étape à partir des solutions optimales des sous-problèmes.
Approches de la Programmation Dynamique
Top-Down avec Mémoïsation
L'approche top-down avec mémoïsation se base sur la décomposition du problème original en plusieurs sous-problèmes. Chaque sous-problème est résolu une seule fois, et son résultat est sauvegardé dans une table de mémoïsation pour éviter les recalculs. Cela améliore considérablement l'efficacité par rapport à une approche récursive naïve qui pourrait recalculer le même sous-problème plusieurs fois.
Bottom-Up
L'approche bottom-up construit la solution du problème à partir des plus petits sous-problèmes. Les résultats des sous-problèmes sont combinés pour résoudre des problèmes plus grands, jusqu'à la résolution complète du problème initial. Cette méthode utilise généralement une table pour stocker l’état de chaque sous-problème.
Applications Pratiques
Problème du sac à dos (Knapsack)
Dans le problème du sac à dos, l'objectif est de maximiser la valeur totale dans le sac tout en respectant une contrainte de poids maximale. La programmation dynamique permet de résoudre efficacement ce problème, notamment dans sa version intégrale, en utilisant à la fois des approches top-down et bottom-up.
Problème de la plus longue sous-séquence commune (LCS)
Le problème de la plus longue sous-séquence commune consiste à trouver la plus longue séquence qui peut apparaître dans deux chaînes. La DP est utilisée pour construire une table qui stocke la longueur des sous-séquences communes jusqu'à l'index actuel des chaînes.
A retenir :
La programmation dynamique est une technique puissante pour résoudre des problèmes complexes par la décomposition en sous-problèmes plus simples. Comprendre les principes de mémoïsation et de sous-structure optimale est crucial pour appliquer efficacement la DP. Les approches top-down et bottom-up permettent d'optimiser les calculs et de garantir une solution efficace aux problèmes classiques tels que le sac à dos et la LCS.
