Programmation dynamique top-down
Définition : Programmation dynamique top-down
La programmation dynamique top-down est une technique pour optimiser les fonctions récursives. Elle consiste à stocker les résultats des appels récursifs dans une table de mémoire, afin d'éviter de recalculer les mêmes valeurs plusieurs fois. Cette technique est appelée mémoisation.
Principe fondamental
La mémoisation suit le principe : "Ne calcule jamais deux fois la même chose". Chaque résultat de fonction est mis en cache, et les appels ultérieurs avec les mêmes paramètres utilisent la valeur mise en cache plutôt que de recalculer.
Exemple classique : La suite de Fibonacci
La suite de Fibonacci
La suite de Fibonacci est définie par :
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) pour n ≥ 2
Version récursive naïve (sans optimisation)
def fibonacci_naif(n):
"""Version récursive naïve - Très inefficace pour n > 30"""
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_naif(n-1) + fibonacci_naif(n-2)
# Exemple d'utilisation
print(fibonacci_naif(10)) # 55
# Attention: fibonacci_naif(40) prendra plusieurs secondes !Problème de la version naïve
La version récursive naïve recalcule sans cesse les mêmes valeurs. Par exemple, pour calculer F(5) :
- F(5) appelle F(4) et F(3)
- F(4) appelle F(3) et F(2)
- F(3) est calculé deux fois !
- F(2) est calculé trois fois !
Complexité temporelle : O(2ⁿ) - exponentielle !
Complexité spatiale : O(n) - due à la pile d'appels récursifs.
Solution avec mémoisation
Optimisation
Fibonacci avec mémoisation
Voici un exemple de code Python qui utilise la mémoisation pour calculer les nombres de Fibonacci de manière récursive :
# Version 1 : Dictionnaire global
memo = {}
def fibonacci_memo(n):
"""Version avec mémoisation - Utilise un dictionnaire global"""
if n in memo:
return memo[n]
if n == 0:
return 0
elif n == 1:
return 1
else:
memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
return memo[n]
# Test
print(fibonacci_memo(100)) # Résultat instantané : 354224848179261915075Explication du code :
- La table de mémoire est stockée dans un dictionnaire appelé memo.
- Avant de calculer la valeur d'un nombre de Fibonacci, on vérifie d'abord si la valeur a déjà été calculée et stockée dans la table de mémoire (
if n in memo). - Si c'est le cas, on renvoie simplement la valeur stockée.
- Sinon, on calcule la valeur récursivement et on stocke la valeur calculée dans la table de mémoire avant de la renvoyer.
Version plus élégante avec décorateur
# Version 2 : Décorateur personnalisé
def memoize(func):
"""Décorateur de mémoisation générique"""
cache = {}
def wrapper(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrapper
@memoize
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(100)) # 354224848179261915075Décorateur @lru_cache
Python propose un décorateur intégré dans le module functools :
from functools import lru_cache
@lru_cache(maxsize=128) # maxsize = taille maximale du cache
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(100)) # 354224848179261915075
print(fibonacci.cache_info()) # CacheInfo(hits=98, misses=101, maxsize=128, currsize=101)lru_cache signifie "Least Recently Used cache" - il évince automatiquement les entrées les moins récemment utilisées quand le cache atteint sa taille maximale.
Comparaison des performances
| Version | Complexité temporelle | Complexité spatiale | Temps pour n=40 |
|---|---|---|---|
| Récursive naïve | O(2ⁿ) - exponentielle | O(n) - pile d'appels | ≈ 30 secondes |
| Avec mémoisation | O(n) - linéaire | O(n) - cache + pile | ≈ 0.001 seconde |
| Itérative (bottom-up) | O(n) - linéaire | O(1) - constant | ≈ 0.0005 seconde |
Visualisation de l'arbre d'appels
Sans mémoisation (F(5)):
F(5)
├── F(4)
│ ├── F(3)
│ │ ├── F(2)
│ │ │ ├── F(1)
│ │ │ └── F(0)
│ │ └── F(1)
│ └── F(2)
│ ├── F(1)
│ └── F(0)
└── F(3)
├── F(2)
│ ├── F(1)
│ └── F(0)
└── F(1)
Total: 15 appels (2^(n+1)-1)
Avec mémoisation (F(5)):
F(5)
├── F(4) (calculé)
│ ├── F(3) (calculé)
│ │ ├── F(2) (calculé)
│ │ │ ├── F(1) (base)
│ │ │ └── F(0) (base)
│ │ └── F(1) (cache)
│ └── F(2) (cache)
└── F(3) (cache)
Total: 6 appels uniques (n+1)Autres exemples d'utilisation
1. Calcul du nombre de chemins dans une grille
from functools import lru_cache
@lru_cache(maxsize=None)
def chemins(m, n):
"""Nombre de chemins uniques de (0,0) à (m,n) en se déplaçant droite/bas"""
if m == 0 or n == 0:
return 1
return chemins(m-1, n) + chemins(m, n-1)
print(chemins(20, 20)) # 1378465288202. Problème du rendu de monnaie
@lru_cache(maxsize=None)
def rendu_monnaie(montant, pieces):
"""
Nombre de façons de rendre 'montant' avec les pièces données
pieces = tuple de pièces disponibles (ex: (1, 2, 5, 10))
"""
if montant == 0:
return 1
if montant < 0 or not pieces:
return 0
# Soit on utilise la première pièce, soit on ne l'utilise pas
return rendu_monnaie(montant - pieces[0], pieces) + \
rendu_monnaie(montant, pieces[1:])
pieces = (1, 2, 5, 10, 20, 50)
print(rendu_monnaie(100, pieces)) # Nombre de façons de faire 100€3. Montée d'escaliers (combien de façons de monter n marches par pas de 1 ou 2)
@lru_cache(maxsize=None)
def escalier(n):
"""Nombre de façons de monter n marches (pas de 1 ou 2)"""
if n <= 1:
return 1
return escalier(n-1) + escalier(n-2)
print([escalier(i) for i in range(10)]) # [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]Avantages et limites de la mémoisation
Avantages
- Réduction drastique du temps d'exécution : passe d'exponentiel à polynomial/linéaire
- Facile à implémenter : quelques lignes de code suffisent
- Préserve la logique récursive : on garde une solution élégante et naturelle
- Fonctionne pour toute fonction pure (déterministe, sans effets de bord)
- Peut être ajoutée progressivement : on peut optimiser seulement les fonctions critiques
- Débogage plus facile que la version itérative complexe
Limites et précautions
- Consommation mémoire : le cache peut devenir très grand
- Pas adapté aux fonctions avec effets de bord ou non-déterministes
- Overhead des appels de fonction : dictionnaire + récursion
- Récursion profonde : peut atteindre la limite de récursion de Python (~1000)
- Fonctions avec paramètres non hashables : ne peuvent pas être utilisées comme clés
- Pas toujours plus rapide : si la fonction est très simple, l'overhead peut dominer
Programmation dynamique : Top-down vs Bottom-up
| Caractéristique | Top-down (Mémoisation) | Bottom-up (Itératif) |
|---|---|---|
| Approche | Part du problème pour arriver aux sous-problèmes | Part des sous-problèmes pour construire la solution |
| Récursion | Oui (appels récursifs) | Non (boucles itératives) |
| Cache | Dictionnaire (stocke seulement les valeurs calculées) | Tableau (pré-rempli, souvent toute la table) |
| Facilité d'implémentation | Plus simple (extension de la version récursive) | Parfois plus complexe (ordre de calcul important) |
| Mémoire | Peut économiser de la mémoire (calcule seulement ce qui est nécessaire) | Remplit souvent tout le tableau même si non nécessaire |
| Performance | Léger overhead du dictionnaire et des appels | Souvent plus rapide (pas d'appels, pas de hash) |
| Risque de récursion | Oui (limite de récursion Python) | Non |
Exemple bottom-up pour Fibonacci
def fibonacci_bottom_up(n):
"""Version itérative (bottom-up) - Optimale en mémoire"""
if n == 0:
return 0
elif n == 1:
return 1
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fibonacci_bottom_up(100)) # 354224848179261915075
# Complexité: O(n) temps, O(1) mémoire ! Exercice pratique
Problème de la somme de sous-ensemble (Subset Sum)
Écrire une fonction qui détermine s'il existe un sous-ensemble d'une liste d'entiers dont la somme est égale à une valeur cible.
Énoncé : Soit une liste d'entiers positifs nombres et une cible somme_cible. Déterminer s'il existe un sous-ensemble (non vide) dont la somme des éléments est exactement somme_cible.
Exemple :
nombres = [3, 34, 4, 12, 5, 2],somme_cible = 9→ True (4 + 5 = 9)nombres = [3, 34, 4, 12, 5, 2],somme_cible = 30→ False
Implémentez une solution avec mémoisation (top-down).
Solution avec mémoisation
from functools import lru_cache
def subset_sum(nombres, somme_cible):
"""
Vérifie s'il existe un sous-ensemble de 'nombres' dont la somme est 'somme_cible'
"""
@lru_cache(maxsize=None)
def solve(i, reste):
"""
i: indice courant dans la liste
reste: somme qu'il reste à atteindre
"""
# Cas de base
if reste == 0:
return True
if i >= len(nombres) or reste < 0:
return False
# Deux choix:
# 1. Inclure l'élément courant
# 2. Ne pas inclure l'élément courant
return solve(i + 1, reste - nombres[i]) or solve(i + 1, reste)
return solve(0, somme_cible)
# Tests
print(subset_sum((3, 34, 4, 12, 5, 2), 9)) # True
print(subset_sum((3, 34, 4, 12, 5, 2), 30)) # False
# Version avec affichage des solutions
def subset_sum_with_solution(nombres, somme_cible):
@lru_cache(maxsize=None)
def solve(i, reste):
if reste == 0:
return (True, ())
if i >= len(nombres) or reste < 0:
return (False, None)
# Essayer d'inclure nombres[i]
included = solve(i + 1, reste - nombres[i])
if included[0]:
return (True, (nombres[i],) + included[1])
# Essayer sans inclure
return solve(i + 1, reste)
return solve(0, somme_cible)
trouve, solution = subset_sum_with_solution((3, 34, 4, 12, 5, 2), 9)
if trouve:
print(f"Solution trouvée : {solution}") # (4, 5)Explication :
- On utilise un décorateur
lru_cachepour mémoiser les résultats intermédiaires. - La fonction récursive explore deux possibilités à chaque étape : inclure ou non l'élément courant.
- Les cas de base sont : somme atteinte (True), plus d'éléments ou somme négative (False).
- La mémoisation évite d'explorer plusieurs fois les mêmes combinaisons (i, reste).
- Complexité temporelle : O(n × somme_cible) au lieu de O(2ⁿ) pour la version naïve.
Bonnes pratiques pour la mémoisation
Conseils d'implémentation
- Utiliser @lru_cache de préférence à un dictionnaire manuel (optimisé, avec stats, gestion de taille)
- Attention aux paramètres mutables : utiliser des tuples plutôt que des listes comme arguments
- Nettoyer le cache si nécessaire :
fibonacci.cache_clear() - Analyser les stats :
fibonacci.cache_info()pour voir l'efficacité - Pour les problèmes à grande échelle, préférer l'approche bottom-up pour éviter la récursion
- Adapter maxsize selon la mémoire disponible et le problème
Exemple avec analyse des performances
from functools import lru_cache
import time
@lru_cache(maxsize=128)
def fibonacci(n):
if n < 2:
return n
return fibonacci(n-1) + fibonacci(n-2)
# Mesure des performances
start = time.time()
resultat = fibonacci(100)
end = time.time()
print(f"Résultat: {resultat}")
print(f"Temps: {(end-start)*1000:.2f} ms")
print(f"Stats cache: {fibonacci.cache_info()}")
# Stats cache: CacheInfo(hits=98, misses=101, maxsize=128, currsize=101)Points clés à retenir
- La mémoisation est une technique d'optimisation pour les fonctions récursives
- Elle stocke les résultats déjà calculés pour éviter les redondances
- La complexité passe souvent d'exponentielle à polynomiale/linéaire
- Python propose
@lru_cachedans le modulefunctoolspour une implémentation optimale - La programmation dynamique existe en deux variantes : top-down (mémoisation) et bottom-up (itératif)
- La mémoisation s'applique à toute fonction pure (déterministe, sans effets de bord)
- Il faut trouver un équilibre entre temps d'exécution et utilisation mémoire
- La version bottom-up est souvent plus économe en mémoire et plus rapide, mais parfois plus complexe à concevoir
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.