algorithm
Anwendungen der dynamischen Programmierung
Suche…
Einführung
Die Grundidee der dynamischen Programmierung besteht darin, ein komplexes Problem auf mehrere kleine und einfache Probleme zu reduzieren, die wiederholt werden. Wenn Sie ein einfaches Unterproblem identifizieren können, das wiederholt berechnet wird, stehen die Chancen für eine dynamische Programmierung des Problems.
Da sich dieses Thema unter Anwendungen der dynamischen Programmierung befindet , konzentriert es sich mehr auf Anwendungen als auf die Erstellung dynamischer Programmieralgorithmen.
Bemerkungen
Definitionen
Memoization - Eine Optimierungstechnik, die hauptsächlich zur Beschleunigung von Computerprogrammen verwendet wird, indem die Ergebnisse teurer Funktionsaufrufe gespeichert und das zwischengespeicherte Ergebnis zurückgegeben wird, wenn dieselben Eingaben erneut auftreten.
Dynamische Programmierung - eine Methode zur Lösung eines komplexen Problems, indem es in eine Sammlung einfacherer Unterprobleme zerlegt wird, jedes dieser Unterprobleme nur einmal gelöst wird und seine Lösungen gespeichert werden.
Fibonacci-Zahlen
Fibonacci-Zahlen sind ein Hauptthema für dynamisches Programmieren, da der traditionelle rekursive Ansatz viele Berechnungen durchführt. In diesen Beispielen werde ich den Basisfall von f(0) = f(1) = 1 .
Hier ist ein Beispiel eines rekursiven Baums für fibonacci(4) . Beachten Sie die wiederholten Berechnungen: 
Nichtdynamische Programmierung O(2^n) Laufzeitkomplexität, O(n) Stackkomplexität
def fibonacci(n):
if n < 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
Dies ist die intuitivste Art, das Problem zu schreiben. Der Stapelspeicherplatz wird höchstens O(n) wenn Sie den ersten rekursiven Zweig herabsteigen und fibonacci(n-1) bis Sie den Basisfall n < 2 treffen.
Der O(2^n) Laufzeitkomplexitätsbeweis, den Sie hier sehen können: Berechnungskomplexität der Fibonacci-Sequenz . Zu beachten ist vor allem, dass die Laufzeit exponentiell ist. Dies bedeutet, dass sich die Laufzeit für jeden nachfolgenden Begriff verdoppelt. fibonacci(15) dauert doppelt so lange wie fibonacci(14) .
Memoized O(n) Laufzeitkomplexität, O(n) Speicherplatzkomplexität , O(n) Stack-Komplexität
memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1
def fibonacci(n):
if len(memo) > n:
return memo[n]
result = fibonacci(n-1) + fibonacci(n-2)
memo.append(result) # f(n) = f(n-1) + f(n-2)
return result
Mit dem memoisierten Ansatz führen wir ein Array ein, das als alle vorherigen Funktionsaufrufe betrachtet werden kann. Die memo[n] ist das Ergebnis des Funktionsaufrufs fibonacci(n) . Dadurch können wir die Raumkomplexität von O(n) gegen eine O(n) -Laufzeit tauschen, da keine doppelten Funktionsaufrufe mehr berechnet werden müssen.
Iterative dynamische Programmierung O(n) Laufzeitkomplexität, O(n) Speicherplatzkomplexität , Kein rekursiver Stack
def fibonacci(n):
memo = [1,1] # f(0) = 1, f(1) = 1
for i in range(2, n+1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]
Wenn wir das Problem in seine Kernelemente zerlegen, werden Sie feststellen, dass wir zur Berechnung von fibonacci(n) fibonacci(n-1) und fibonacci(n-2) benötigen. Wir können auch feststellen, dass unser Basisfall am Ende dieses rekursiven Baums angezeigt wird (siehe oben).
Mit diesen Informationen ist es jetzt sinnvoll, die Lösung rückwärts zu berechnen, beginnend mit den Basisfällen und nach oben. Um nun fibonacci(n) zu berechnen, berechnen wir zunächst alle Fibonacci-Zahlen bis und durch n .
Der Hauptvorteil hier ist, dass wir den rekursiven Stack jetzt unter Beibehaltung der O(n) -Laufzeit eliminiert haben. Leider haben wir immer noch eine O(n) -Kammerkomplexität, die aber auch geändert werden kann.
Erweiterte iterative dynamische Programmierung O(n) Laufzeitkomplexität, O(1) Speicherplatzkomplexität , Kein rekursiver Stack
def fibonacci(n):
memo = [1,1] # f(1) = 1, f(2) = 1
for i in range (2, n):
memo[i%2] = memo[0] + memo[1]
return memo[n%2]
Wie oben erwähnt, beginnt der iterative dynamische Programmierungsansatz mit den Basisfällen und arbeitet bis zum Endergebnis. Um die räumliche Komplexität von O(1) (konstant) zu erreichen, müssen wir die gleiche Beobachtung machen, die wir für den rekursiven Stapel gemacht haben - wir brauchen nur fibonacci(n-1) und fibonacci(n-2) , um zu bauen fibonacci(n) . Dies bedeutet, dass wir die Ergebnisse für fibonacci(n-1) und fibonacci(n-2) an jedem Punkt unserer Iteration nur speichern müssen.
Um diese letzten 2 Ergebnisse zu speichern, verwende ich ein Array der Größe 2 und blättere einfach den mit i % 2 zuzuweisenden Index, der abwechselnd wie folgt verwendet wird: 0, 1, 0, 1, 0, 1, ..., i % 2 .
Ich füge beide Indizes des Arrays zusammen, weil wir wissen, dass die Addition kommutativ ist ( 5 + 6 = 11 und 6 + 5 == 11 ). Das Ergebnis wird dann dem älteren der beiden Punkte zugewiesen (mit i % 2 ). Das Endergebnis wird dann an der Position n%2 gespeichert
Anmerkungen
- Es ist wichtig anzumerken, dass es manchmal am besten ist, eine iterative Lösung für Funktionen zu entwickeln, die wiederholt umfangreiche Berechnungen durchführt, da Sie einen Cache für die Antwort auf die Funktionsaufrufe aufbauen und nachfolgende Aufrufe
O(1)if sein können es wurde bereits berechnet.
