|
La mémorisation est une technique d'optimisation cruciale utilisée dans la programmation dynamique pour améliorer considérablement l'efficacité. Il fonctionne en stockant les résultats d'appels de fonctions coûteux et en renvoyant le résultat mis en cache lorsque les mêmes entrées se reproduisent. Cela évite les calculs redondants, conduisant à une accélération considérable, en particulier pour les problèmes comportant des sous-problèmes qui se chevauchent.
Voici comment il est utilisé :
1. Identifier les sous-problèmes qui se chevauchent : La programmation dynamique résout les problèmes en les décomposant en sous-problèmes plus petits et se chevauchant. Si le même sous-problème se produit plusieurs fois, la mémorisation peut empêcher le recalcul.
2. Stockage des résultats : Une structure de données, généralement une table de hachage (dictionnaire en Python) ou un tableau, est utilisée pour stocker les résultats des sous-problèmes. L'entrée du sous-problème (par exemple, les paramètres d'une fonction récursive) sert de clé et le résultat calculé est la valeur.
3. Vérification des résultats mis en cache : Avant de calculer la solution à un sous-problème, l'algorithme vérifie le stockage pour voir si le résultat est déjà disponible. Si tel est le cas, le résultat mis en cache est renvoyé immédiatement.
4. Stockage et renvoi des résultats : Si le résultat n'est pas mis en cache, l'algorithme le calcule, le stocke dans la structure de données, puis le renvoie.
Exemple (séquence de Fibonacci) :
Une solution récursive naïve pour la séquence de Fibonacci est très inefficace en raison des calculs répétés. La mémorisation améliore considérablement cela :
Solution récursive naïve (inefficace) :
```python
def fibonacci_naive(n):
si n <=1 :
retour m
retourner fibonacci_naive(n-1) + fibonacci_naive(n-2)
```
Solution récursive mémorisée :
```python
memo ={} # Dictionnaire pour la mémorisation
def fibonacci_memo(n):
si n dans le mémo :
renvoyer le mémo[n]
si n <=1 :
résultat =n
autre:
résultat =fibonacci_memo(n-1) + fibonacci_memo(n-2)
mémo[n] =résultat
résultat de retour
```
Dans la version mémorisée :
* `memo` stocke les nombres de Fibonacci précédemment calculés.
* Avant de faire un appel récursif, `fibonacci_memo` vérifie si le résultat pour `n` est déjà dans `memo`.
* Si c'est le cas, la valeur stockée est renvoyée directement. Sinon, le résultat est calculé, stocké dans `memo`, puis renvoyé.
Ce changement transforme un algorithme à temps exponentiel en un algorithme à temps linéaire. La clé est d’éviter les calculs redondants des mêmes nombres de Fibonacci plusieurs fois.
En substance : La mémorisation transforme une approche de programmation dynamique descendante (récursive) en une approche plus efficace en mettant en cache les résultats intermédiaires. Il complète les approches de tabulation (ascendantes), qui évitent également les calculs redondants mais utilisent des méthodes itératives plutôt que récursives. Le choix entre la mémorisation et la tabulation dépend souvent du problème spécifique et des préférences du programmeur ; les deux atteignent le même objectif :éviter les calculs redondants.
|
