Memoisierung ist eine entscheidende Optimierungstechnik, die bei der dynamischen Programmierung verwendet wird, um die Effizienz erheblich zu verbessern. Es funktioniert, indem es die Ergebnisse teurer Funktionsaufrufe speichert und das zwischengespeicherte Ergebnis zurückgibt, wenn dieselben Eingaben erneut auftreten. Dies vermeidet redundante Berechnungen, was zu einer dramatischen Beschleunigung führt, insbesondere bei Problemen mit überlappenden Unterproblemen.
So wird es genutzt:
1. Identifizieren überlappender Unterprobleme: Die dynamische Programmierung löst Probleme, indem sie sie in kleinere, überlappende Unterprobleme zerlegt. Wenn das gleiche Teilproblem mehrmals auftritt, kann eine Memoisierung eine Neuberechnung verhindern.
2. Ergebnisse speichern: Eine Datenstruktur, normalerweise eine Hash -Tabelle (Wörterbuch in Python) oder ein Array, wird verwendet, um die Ergebnisse von Teilproblemen zu speichern. Die Eingabe in das Unterproblem (z. B. die Parameter einer rekursiven Funktion) dient als Schlüssel, und das berechnete Ergebnis ist der Wert.
3. nach zwischengespeicherten Ergebnissen untersuchen: Vor der Berechnung der Lösung für ein Teilproblem überprüft der Algorithmus den Speicher, um festzustellen, ob das Ergebnis bereits verfügbar ist. Wenn dies der Fall ist, wird das zwischengespeicherte Ergebnis sofort zurückgegeben.
4. Wenn das Ergebnis nicht zwischengespeichert wird, berechnet der Algorithmus es, speichert es in der Datenstruktur und gibt es dann zurück.
Beispiel (Fibonacci -Sequenz):
Eine naive rekursive Lösung für die Fibonacci -Sequenz ist aufgrund wiederholter Berechnungen sehr ineffizient. Memoisierung verbessert dies drastisch:
naive (ineffiziente) rekursive Lösung:
`` `Python
Def fibonacci_naive (n):
Wenn n <=1:
Rückkehr n
return fibonacci_naive (n-1) + fibonacci_naive (n-2)
`` `
rekursive Memo -Lösung:
`` `Python
memo ={} # Dictionary für die Memoisierung
Def fibonacci_memo (n):
Wenn n in Memo:
Return Memo [n]
Wenn n <=1:
Ergebnis =n
anders:
result =fibonacci_memo (n-1) + fibonacci_memo (n-2)
Memo [n] =Ergebnis
Rückgabeergebnis
`` `
In der memoisierten Version:
* `memo` speichert zuvor berechnete Fibonacci -Zahlen.
* Bevor Sie einen rekursiven Anruf tätigen, überprüft `fibonacci_memo`, ob das Ergebnis für` n` bereits in `memo` liegt.
* Wenn dies der Fall ist, wird der gespeicherte Wert direkt zurückgegeben. Andernfalls wird das Ergebnis berechnet, in "Memo" gespeichert und dann zurückgegeben.
Diese Änderung verwandelt einen Exponential-Zeit-Algorithmus in einen linearen Algorithmus. Der Schlüssel besteht darin, die redundanten Berechnungen derselben Fibonacci -Zahlen mehrmals zu vermeiden.
im Wesentlichen: Die Memoisierung verwandelt einen dynamischen Programmieransatz von Top-Down (rekursiv) in einen effizienteren, durch Zwischenspeichern Zwischenergebnisse. Es ergänzt die Tabellierungsansätze (Bottom-up), die auch redundante Berechnungen vermeiden, aber iterative Methoden anstelle von Rekursion verwenden. Die Auswahl zwischen Memoisierung und Tabelle hängt häufig von dem spezifischen Problem und dem Programmiererpräferenz ab. Beide erreichen das gleiche Ziel, redundante Berechnungen zu vermeiden.
