|
La mémorisation améliore considérablement l'efficacité des algorithmes de programmation dynamique en évitant les calculs redondants. La programmation dynamique résout les problèmes en les décomposant en sous-problèmes plus petits qui se chevauchent, en résolvant chaque sous-problème une seule fois et en stockant leurs solutions. La mémorisation est une approche descendante pour y parvenir.
Voici comment cela fonctionne :
1. Structure récursive : Les problèmes de programmation dynamique se prêtent souvent à des solutions récursives. Une implémentation récursive naïve calculerait à plusieurs reprises les solutions aux mêmes sous-problèmes, conduisant à une complexité temporelle exponentielle.
2. Stockage des résultats : La mémorisation introduit une structure de données (généralement une table de hachage ou un tableau) pour stocker les solutions aux sous-problèmes déjà calculés. Cette structure est souvent appelée « mémo » ou « cache ».
3. Vérification du mémo : Avant de résoudre récursivement un sous-problème, l’algorithme vérifie d’abord le mémo. Si la solution est déjà présente (ce qui signifie que le sous-problème a déjà été résolu), elle est récupérée directement à partir du mémo, évitant ainsi un nouveau calcul.
4. Stockage du résultat : Si la solution n'est pas trouvée dans le mémo, l'algorithme résout le sous-problème de manière récursive, puis *stocke* le résultat dans le mémo avant de le renvoyer.
Exemple :
Considérez le calcul de la séquence de Fibonacci. Une approche récursive naïve a une complexité exponentielle car elle recalcule plusieurs fois de nombreux nombres de Fibonacci. Avec mémorisation :
```python
memo ={} # Initialiser le mémo
def fibonacci_memo(n):
si n dans le mémo :
return memo[n] # Récupérer du mémo si déjà calculé
si n <=1 :
retour m
autre:
résultat =fibonacci_memo(n-1) + fibonacci_memo(n-2)
memo[n] =result # Stocke le résultat dans le mémo
résultat de retour
print(fibonacci_memo(5)) # Sortie :5
```
Dans cet exemple, « memo » stocke les nombres de Fibonacci calculés. Lorsque `fibonacci_memo(5)` est appelé, il appelle récursivement `fibonacci_memo(4)` et `fibonacci_memo(3)`. `fibonacci_memo(3)` appellera récursivement `fibonacci_memo(2)` et `fibonacci_memo(1)`. Cependant, une fois que « fibonacci_memo(1) » ou « fibonacci_memo(2) » est calculé et stocké dans « memo », les appels ultérieurs à ces mêmes sous-problèmes renverront directement les résultats stockés, évitant ainsi les calculs redondants. Cela réduit la complexité temporelle d’exponentielle à linéaire.
Essentiellement, la mémorisation transforme un algorithme récursif potentiellement exponentiel en un algorithme en temps linéaire (ou en temps polynomial dans d'autres cas) en exploitant la puissance de la mise en cache des résultats précédemment calculés. Il s'agit d'une technique d'optimisation puissante fréquemment utilisée en conjonction avec une programmation dynamique pour améliorer l'efficacité.
|
