Dynamische Programmierung ist eine Computerprogrammiertechnik, die dabei hilft, eine Klasse von Problemen mit überlappenden Teilproblemen und optimalen Teilstruktureigenschaften effizient zu lösen.
Solche Probleme umfassen das wiederholte Berechnen des Werts derselben Teilprobleme, um die optimale Lösung zu finden.
Dynamisches Programmierbeispiel
Nehmen wir den Fall der Generierung der Fibonacci-Folge .
Wenn die Folge F(1) F(2) F(3) ........ F(50) ist, dann folgt die 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 hier überlappende Teilprobleme gibt, da wir F(48) berechnen müssen, um sowohl F(50) als auch F(49) zu berechnen. Dies ist genau der Algorithmus, bei dem ein Beispiel für dynamische Programmierung deutlich sichtbar ist.
Wie die dynamische Programmierung funktioniert
Dynamische Programmierung funktioniert, indem die Ergebnisse von Teilproblemen gespeichert werden, sodass sie zur Hand sind, wenn ihre Lösungen benötigt werden, und wir sie nicht neu berechnen müssen.
Diese Technik, den Wert von Teilaufgaben zu speichern, wird Memoisierung (Erinnern) genannt. Indem wir die Werte in einem Array speichern, sparen wir Zeit für die Berechnung von Teilproblemen, auf die wir bereits gestoßen sind.
var m = map(0 → 0, 1 → 1)
function fib(n)
if key n is not in map m
m[n] = fib(n − 1) + fib(n − 2)
return m[n]
Dynamic Programming by Memoization ist ein Top-Down-Ansatz zur dynamischen Programmierung. Indem wir die Arbeitsrichtung des Algorithmus umkehren, d. h. vom Basisfall ausgehen und auf die Lösung hinarbeiten, können wir auch Bottom-Up Dynamic Programming verwenden.
function fib(n)
if n = 0
return 0
else
var prevFib = 0, currFib = 1
repeat n − 1 times
var newFib = prevFib + currFib
prevFib = currFib
currFib = newFib
return currentFib
Rekursion vs. dynamische Programmierung
Dynamische Programmierung wird hauptsächlich auf rekursive Algorithmen angewendet. Dies ist kein Zufall, die meisten Optimierungsprobleme erfordern Rekursion, und zur Optimierung wird dynamische Programmierung verwendet.
Aber nicht alle Aufgaben, die Rekursion verwenden, können die dynamische Programmierung verwenden. Wenn es keine überlappenden Teilprobleme gibt, wie im Fall der Fibonacci-Folge, kann die Rekursion nur mit einem Teile-und-Herrsche-Ansatz zu einer Lösung führen.
Aus diesem Grund kann ein rekursiver Algorithmus wie "Merge Sort" keine dynamische Programmierung verwenden, da sich die Teilaufgaben in keiner Weise überschneiden.
Gierige vs. dynamische Programmierung
Gierige Algorithmen ähneln der dynamischen Programmierung insofern, als sie beide Optimierungswerkzeuge sind.
Ein gieriger Algorithmus sucht jedoch nach einer lokal optimalen Lösung, oder mit anderen Worten, einer "gierigen" Wahl in der Hoffnung, ein globales Optimum zu finden. Daher können gierige Algorithmen eine Vermutung anstellen, die optimal aussieht, aber gleichzeitig teuer wird und das Finden eines globalen Optimums nicht garantiert.
Die dynamische Programmierung hingegen findet die optimale Lösung für Teilprobleme und trifft dann eine fundierte Wahl, indem sie die Ergebnisse dieser Teilprobleme kombiniert, um die optimalste Lösung zu finden.
