In diesem Tutorial erfahren Sie, was dynamische Programmierung ist. Außerdem finden Sie den Vergleich zwischen dynamischer Programmierung und gierigen Algorithmen zur Lösung von Problemen.
Dynamische Programmierung ist eine Technik in der Computerprogrammierung, mit deren Hilfe eine Klasse von Problemen mit überlappenden Teilproblemen und optimalen Eigenschaften der Unterstruktur effizient gelöst werden kann.
Solche Probleme beinhalten das wiederholte Berechnen des Wertes derselben Teilprobleme, um die optimale Lösung zu finden.
Beispiel für eine dynamische Programmierung
Nehmen Sie den Fall der Erzeugung der Fibonacci-Sequenz.
Wenn die Folge F (1) F (2) F (3)… F (50) ist, folgt sie der Regel F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Beachten Sie, dass es überlappende Teilprobleme gibt. Wir müssen F (48) berechnen, um sowohl F (50) als auch F (49) zu berechnen. Dies ist genau die Art von Algorithmus, bei der die dynamische Programmierung glänzt.
So funktioniert dynamische Programmierung
Bei der dynamischen Programmierung werden die Ergebnisse von Teilproblemen so gespeichert, dass sie bei Bedarf zur Hand sind und wir sie nicht neu berechnen müssen.
Diese Technik zum Speichern des Werts von Teilproblemen wird als Memoisierung bezeichnet. Durch das Speichern der Werte im Array sparen wir Zeit für die Berechnung von Unterproblemen, auf die wir bereits gestoßen sind.
var m = Map (0 → 0, 1 → 1) Funktion fib (n), wenn Schlüssel n nicht in Map ist mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Dynamische Programmierung durch Memoisierung ist ein Top-Down-Ansatz für die dynamische Programmierung. Indem wir die Richtung umkehren, in der der Algorithmus arbeitet, dh indem wir vom Basisfall ausgehen und auf die Lösung hinarbeiten, können wir die dynamische Programmierung auch von unten nach oben implementieren.
Funktion fib (n) wenn n = 0 0 zurückgeben sonst var prevFib = 0, currFib = 1 n - 1 mal wiederholen var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Rekursion vs dynamische Programmierung
Die dynamische Programmierung wird hauptsächlich auf rekursive Algorithmen angewendet. Dies ist kein Zufall, die meisten Optimierungsprobleme erfordern eine Rekursion und die dynamische Programmierung wird zur Optimierung verwendet.
Aber nicht alle Probleme, die Rekursion verwenden, können die dynamische Programmierung verwenden. Wenn keine überlappenden Teilprobleme wie beim Fibonacci-Sequenzproblem vorliegen, kann eine Rekursion die Lösung nur mithilfe eines Divide-and-Conquer-Ansatzes erreichen.
Dies ist der Grund, warum ein rekursiver Algorithmus wie Merge Sort keine dynamische Programmierung verwenden kann, da sich die Teilprobleme in keiner Weise überlappen.
Gierige Algorithmen gegen dynamische Programmierung
Gierige Algorithmen ähneln der dynamischen Programmierung in dem Sinne, dass sie beide Werkzeuge zur Optimierung sind.
Gierige Algorithmen suchen jedoch nach lokal optimalen Lösungen oder mit anderen Worten nach einer gierigen Wahl, in der Hoffnung, ein globales Optimum zu finden. Daher können gierige Algorithmen eine Vermutung anstellen, die zu diesem Zeitpunkt optimal aussieht, aber später teuer wird und kein globales Optimum garantiert.
Die dynamische Programmierung hingegen findet die optimale Lösung für Teilprobleme und trifft dann eine fundierte Entscheidung, um die Ergebnisse dieser Teilprobleme zu kombinieren und die optimalste Lösung zu finden.
