Introduction à la programmation dynamique
La programmation dynamique est une méthode algorithmique utilisée pour résoudre des problèmes d'optimisation, en particulier ceux qui présentent une structure de sous-problèmes imbriqués ou une nature récursive. Elle s'appuie sur la décomposition d'un problème complexe en sous-problèmes plus petits, en stockant les solutions intermédiaires pour éviter de les recalculer à chaque étape.
La programmation dynamique repose sur deux concepts clés :
- Sous-structure optimale : Une solution optimale du problème global contient des solutions optimales à ses sous-problèmes.
- Sous-problèmes superposés : Les mêmes sous-problèmes sont résolus plusieurs fois dans l'approche récursive naïve.
En exploitant ces propriétés, la programmation dynamique évite les calculs redondants et réduit considérablement la complexité temporelle.
Les deux approches de la programmation dynamique
La programmation dynamique suit deux approches principales :
Top-down (Mémoïsation)
Cette approche commence par résoudre le problème initial et s'appuie sur la résolution récursive des sous-problèmes. Elle utilise une structure de données (comme un tableau ou un dictionnaire) pour stocker les résultats des sous-problèmes déjà résolus, évitant ainsi les calculs redondants.
Caractéristiques :
- Récursive (appels récursifs)
- Cache (mémorisation) des résultats
- Ne calcule que les sous-problèmes nécessaires
- Plus naturelle à implémenter à partir de la solution récursive
Exemple avec Fibonacci :
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]Bottom-up (Tabulation)
Cette approche consiste à résoudre d'abord les sous-problèmes les plus simples et à progresser vers la résolution du problème initial. Elle construit une table de solutions aux sous-problèmes en ordre croissant de complexité, en utilisant les résultats précédents pour résoudre les problèmes suivants.
Caractéristiques :
- Itérative (boucles)
- Tableau rempli systématiquement
- Calcule tous les sous-problèmes (même ceux non nécessaires)
- Souvent plus efficace (pas d'overhead de récursion)
Exemple avec Fibonacci :
def fibonacci_tabu(n):
if n < 2:
return n
tab = [0] * (n + 1)
tab[1] = 1
for i in range(2, n + 1):
tab[i] = tab[i-1] + tab[i-2]
return tab[n]Comparaison Top-down vs Bottom-up
| Caractéristique | Top-down (Mémoïsation) | Bottom-up (Tabulation) |
|---|---|---|
| Nature | Récursive | Itérative |
| Ordre de calcul | À la demande (lazy) | Systématique (eager) |
| Stockage | Cache partiel (seulement les valeurs calculées) | Tableau complet (souvent toutes les valeurs) |
| Risques | Dépassement de pile (récursion profonde) | Calcul inutile de sous-problèmes non nécessaires |
| Facilité d'implémentation | Plus simple à partir de la version récursive | Parfois plus complexe à concevoir |
Applications et importance de la programmation dynamique
La programmation dynamique est un outil puissant et polyvalent pour résoudre divers problèmes d'optimisation et de recherche. Ses applications et son importance sont largement reconnues dans de nombreux domaines :
La programmation dynamique est couramment utilisée pour concevoir des algorithmes efficaces pour résoudre des problèmes complexes :
- Recherche du plus court chemin (Floyd-Warshall, Bellman-Ford)
- Plus longue sous-séquence commune (LCS)
- Problème du sac à dos (Knapsack)
- Multiplication de chaînes de matrices
- Partitionnement de nombres
- Algorithme de Viterbi (traitement du langage)
Dans des domaines tels que la gestion de projets, la logistique et les systèmes de production :
- Optimisation des tâches de planification
- Ordonnancement avec contraintes de temps
- Gestion des ressources limitées
- Optimisation des coûts de production
La programmation dynamique est un élément essentiel de nombreuses techniques d'IA :
- Planification de trajectoires pour les robots
- Apprentissage par renforcement (équation de Bellman)
- Résolution de processus de décision markoviens (MDP)
- Recherche heuristique (algorithme A*)
La programmation dynamique est appliquée à divers problèmes financiers :
- Gestion de portefeuille
- Évaluation d'options (modèle de Black-Scholes)
- Modélisation de décisions d'investissement
- Optimisation sous contraintes budgétaires
Dans le domaine du vivant, la programmation dynamique est essentielle :
- Alignement de séquences (Needleman-Wunsch, Smith-Waterman)
- Recherche de motifs dans l'ADN
- Prédiction de structures de protéines
Optimisation de problèmes concrets :
- Gestion des stocks
- Optimisation des réseaux de transport
- Allocation de ressources
Problèmes classiques résolus par programmation dynamique
| Problème | Description | Complexité |
|---|---|---|
| Suite de Fibonacci | Calcul du n-ième terme de la suite | O(n) |
| Plus long chemin dans une grille | Nombre de chemins de (0,0) à (m,n) | O(m × n) |
| Plus longue sous-séquence commune (LCS) | Trouver la plus longue séquence commune à deux chaînes | O(m × n) |
| Sac à dos (Knapsack) | Maximiser la valeur d'objets sans dépasser la capacité | O(n × capacité) |
| Multiplications de chaînes de matrices | Trouver le parenthésage optimal pour minimiser les opérations | O(n³) |
| Plus courts chemins (Floyd-Warshall) | Distances entre toutes les paires de sommets | O(n³) |
| Édition distance (Levenshtein) | Nombre minimum d'opérations pour transformer une chaîne en une autre | O(m × n) |
| Découpe de tiges (Rod cutting) | Maximiser le profit de la découpe d'une tige | O(n²) |
Exemple détaillé : Problème de la découpe de tiges (Rod cutting)
Découpe de tiges
Énoncé : On dispose d'une tige de longueur n et d'un tableau de prix p[i] pour une tige de longueur i. Déterminer la façon de découper la tige pour maximiser le revenu total.
Exemple : Pour n = 4 et les prix :
- Longueur 1 : 1€
- Longueur 2 : 5€
- Longueur 3 : 8€
- Longueur 4 : 9€
La solution optimale est de découper en deux morceaux de longueur 2 (5€ + 5€ = 10€) plutôt que de vendre la tige entière (9€).
Solution récursive naïve
def rod_cutting_naif(n, prix):
"""
Version récursive naïve - très inefficace (exponentielle)
"""
if n == 0:
return 0
revenu_max = -1
for i in range(1, n + 1):
revenu_max = max(revenu_max, prix[i] + rod_cutting_naif(n - i, prix))
return revenu_max
# Prix indicés de 1 à n (prix[1] = prix pour longueur 1)
prix = [0, 1, 5, 8, 9] # prix[0] est ignoré
print(rod_cutting_naif(4, prix)) # 10Solution avec mémoïsation (Top-down)
def rod_cutting_memo(n, prix, memo=None):
"""
Version avec mémoïsation - O(n²)
"""
if memo is None:
memo = {}
if n == 0:
return 0
if n in memo:
return memo[n]
revenu_max = -1
for i in range(1, n + 1):
revenu_max = max(revenu_max, prix[i] + rod_cutting_memo(n - i, prix, memo))
memo[n] = revenu_max
return revenu_max
prix = [0, 1, 5, 8, 9]
print(rod_cutting_memo(4, prix)) # 10Solution avec tabulation (Bottom-up)
def rod_cutting_tabu(n, prix):
"""
Version avec tabulation - O(n²)
"""
# Tableau des revenus maximaux pour chaque longueur
r = [0] * (n + 1)
# Calcul itératif des solutions
for j in range(1, n + 1):
revenu_max = -1
for i in range(1, j + 1):
revenu_max = max(revenu_max, prix[i] + r[j - i])
r[j] = revenu_max
return r[n]
prix = [0, 1, 5, 8, 9]
print(rod_cutting_tabu(4, prix)) # 10
# Version qui donne aussi la solution (les découpes)
def rod_cutting_with_solution(n, prix):
r = [0] * (n + 1)
s = [0] * (n + 1) # Stocke la taille du premier morceau
for j in range(1, n + 1):
revenu_max = -1
for i in range(1, j + 1):
if revenu_max < prix[i] + r[j - i]:
revenu_max = prix[i] + r[j - i]
s[j] = i
r[j] = revenu_max
# Reconstruction de la solution
decoupes = []
while n > 0:
decoupes.append(s[n])
n -= s[n]
return r[0], decoupes
revenu, decoupes = rod_cutting_with_solution(4, [0, 1, 5, 8, 9])
print(f"Revenu maximal : {revenu}, Découpes : {decoupes}") # [2, 2]Avantages de la programmation dynamique
- Réduction de la complexité temporelle : Transforme des algorithmes exponentiels en algorithmes polynomiaux.
- Évitement des calculs redondants : Grâce à la mémorisation ou à la tabulation, chaque sous-problème n'est résolu qu'une seule fois.
- Solution exacte : Contrairement aux heuristiques, la programmation dynamique garantit une solution optimale.
- Applicabilité large : Peut être appliquée à une grande variété de problèmes d'optimisation.
- Structure claire : La relation de récurrence fournit un cadre mathématique précis.
Limitations de la programmation dynamique
- Consommation mémoire : Le stockage des résultats intermédiaires peut nécessiter beaucoup de mémoire (compromis temps-mémoire).
- Problèmes sans sous-structure optimale : La programmation dynamique ne peut pas être appliquée si cette propriété n'est pas vérifiée.
- Dimensionnalité : Pour les problèmes avec de nombreux paramètres, la table peut devenir trop grande (fléau de la dimension).
- Complexité de conception : Trouver la bonne relation de récurrence et les bons états peut être difficile.
- Non applicable aux problèmes NP-difficiles : Pour les problèmes NP-difficiles comme le TSP, la programmation dynamique reste exponentielle (bien que meilleure que la force brute).
- La programmation dynamique est une méthode d'optimisation pour les problèmes avec sous-structure optimale et sous-problèmes superposés.
- Deux approches : top-down (mémoïsation) et bottom-up (tabulation).
- La mémoïsation est récursive avec cache ; la tabulation est itérative avec tableau.
- La programmation dynamique réduit la complexité temporelle d'exponentielle à polynomiale.
- Applications dans de nombreux domaines : algorithmique, intelligence artificielle, finance, bioinformatique, etc.
- Problèmes classiques : Fibonacci, LCS, sac à dos, plus court chemin, découpe de tiges.
- Compromis temps-mémoire : la programmation dynamique utilise plus de mémoire pour gagner du temps.
- Nécessite de bien identifier les états et la relation de récurrence.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.