Datenstrukturen - Dynamische Programmierung
Der Ansatz der dynamischen Programmierung ähnelt dem Teilen und Erobern, indem das Problem in immer kleinere Unterprobleme unterteilt wird. Aber im Gegensatz zu Teilen und Erobern werden diese Unterprobleme nicht unabhängig voneinander gelöst. Vielmehr werden die Ergebnisse dieser kleineren Unterprobleme gespeichert und für ähnliche oder überlappende Unterprobleme verwendet.
Dynamische Programmierung wird verwendet, wenn wir Probleme haben, die in ähnliche Unterprobleme unterteilt werden können, damit deren Ergebnisse wiederverwendet werden können. Meist werden diese Algorithmen zur Optimierung verwendet. Vor dem Lösen des vorliegenden Unterproblems versucht der dynamische Algorithmus, die Ergebnisse der zuvor gelösten Unterprobleme zu untersuchen. Die Lösungen von Teilproblemen werden kombiniert, um die beste Lösung zu erzielen.
Also können wir das sagen -
Das Problem sollte in kleinere überlappende Unterprobleme unterteilt werden können.
Eine optimale Lösung kann erreicht werden, indem eine optimale Lösung kleinerer Teilprobleme verwendet wird.
Dynamische Algorithmen verwenden Memoization.
Vergleich
Im Gegensatz zu gierigen Algorithmen, bei denen die lokale Optimierung angesprochen wird, sind dynamische Algorithmen für eine Gesamtoptimierung des Problems motiviert.
Im Gegensatz zu Divide- und Conquer-Algorithmen, bei denen Lösungen kombiniert werden, um eine Gesamtlösung zu erhalten, verwenden dynamische Algorithmen die Ausgabe eines kleineren Unterproblems und versuchen dann, ein größeres Unterproblem zu optimieren. Dynamische Algorithmen verwenden Memoization, um sich an die Ausgabe bereits gelöster Unterprobleme zu erinnern.
Beispiel
Die folgenden Computerprobleme können mithilfe eines dynamischen Programmieransatzes gelöst werden:
- Fibonacci-Zahlenreihen
- Rucksackproblem
- Turm von Hanoi
- Alle Paare kürzester Weg von Floyd-Warshall
- Kürzester Weg von Dijkstra
- Projektplanung
Die dynamische Programmierung kann sowohl von oben nach unten als auch von unten nach oben erfolgen. In den meisten Fällen ist es natürlich billiger, sich auf die vorherige Lösungsausgabe zu beziehen, als die CPU-Zyklen neu zu berechnen.