DAA - Dynamische Programmierung
Dynamische Programmierung wird auch bei Optimierungsproblemen verwendet. Wie die Divide-and-Conquer-Methode löst die dynamische Programmierung Probleme, indem sie die Lösungen von Teilproblemen kombiniert. Darüber hinaus löst der dynamische Programmieralgorithmus jedes Unterproblem nur einmal und speichert dann seine Antwort in einer Tabelle, wodurch die Arbeit vermieden wird, die Antwort jedes Mal neu zu berechnen.
Zwei Haupteigenschaften eines Problems legen nahe, dass das angegebene Problem mithilfe der dynamischen Programmierung gelöst werden kann. Diese Eigenschaften sindoverlapping sub-problems and optimal substructure.
Überlappende Unterprobleme
Ähnlich wie beim Divide-and-Conquer-Ansatz kombiniert die dynamische Programmierung auch Lösungen für Unterprobleme. Es wird hauptsächlich verwendet, wenn die Lösung eines Teilproblems wiederholt benötigt wird. Die berechneten Lösungen werden in einer Tabelle gespeichert, sodass diese nicht neu berechnet werden müssen. Daher wird diese Technik benötigt, wenn überlappende Unterprobleme bestehen.
Beispielsweise hat die binäre Suche kein überlappendes Unterproblem. Während rekursives Programm von Fibonacci-Zahlen viele überlappende Unterprobleme aufweist.
Optimale Unterstruktur
Ein gegebenes Problem hat die optimale Substruktur-Eigenschaft, wenn die optimale Lösung des gegebenen Problems unter Verwendung optimaler Lösungen seiner Unterprobleme erhalten werden kann.
Das Problem mit dem kürzesten Pfad weist beispielsweise die folgende optimale Unterstruktureigenschaft auf:
Wenn ein Knoten x liegt auf dem kürzesten Weg von einem Quellknoten u zum Zielknoten v, dann der kürzeste Weg von u zu v ist die Kombination des kürzesten Weges von u zu xund der kürzeste Weg von x zu v.
Die Standardalgorithmen für den kürzesten Pfad aller Paare wie Floyd-Warshall und Bellman-Ford sind typische Beispiele für dynamische Programmierung.
Schritte des dynamischen Programmieransatzes
Der Algorithmus für die dynamische Programmierung besteht aus den folgenden vier Schritten:
- Charakterisieren Sie die Struktur einer optimalen Lösung.
- Definieren Sie rekursiv den Wert einer optimalen Lösung.
- Berechnen Sie den Wert einer optimalen Lösung, normalerweise von unten nach oben.
- Konstruieren Sie aus den berechneten Informationen eine optimale Lösung.
Anwendungen des dynamischen Programmieransatzes
- Matrixkettenmultiplikation
- Längste gemeinsame Folge
- Problem mit dem reisenden Verkäufer