Dynamische Programmierung

Grundprinzip und Voraussetzungen

Dynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems. Dazu wird das Gesamtproblem in Teilprobleme aufgeteilt, deren Zwischenresultate systematisch gespeichert und wiederverwendet werden.

Die Methode eignet sich, wenn ein Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Gesamtproblems aus optimalen Lösungen seiner Teilprobleme zusammengesetzt werden kann. Diese Voraussetzung heißt Optimalitätsprinzip von Bellman. Der Begriff geht auf den amerikanischen Mathematiker Richard Bellman zurück, der die Methode in den 1940er Jahren in der Regelungstheorie einführte.

Vorgehensweise:

• Zuerst werden die optimalen Lösungen der kleinsten Teilprobleme direkt berechnet.
• Diese Lösungen werden zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt.
• Die bereits berechneten Ergebnisse werden in einer Tabelle gespeichert.
• Bei erneut auftretenden gleichartigen Teilproblemen wird auf die gespeicherten Zwischenlösungen zurückgegriffen.
• Das Verfahren wird fortgesetzt, bis das ursprüngliche Problem gelöst ist.

Dadurch entfallen wiederholte Berechnungen. Insbesondere werden kostspielige Rekursionen vermieden, weil bekannte Teilergebnisse wiederverwendet werden. Das senkt die Laufzeit deutlich.

Dynamische Betrachtung in Theorie und Physik

In der Regelungstheorie und verwandten Gebieten kann dynamische Programmierung verwendet werden, um eine Gleichung herzuleiten, deren Lösung den optimalen Wert ergibt. Diese Gleichung heißt Hamilton-Jacobi-Bellman-Gleichung.

Bei einem zeitabhängigen Problem betrachtet man den optimalen Wert der Zielfunktion zu einem bestimmten Zeitpunkt. Anschließend fragt man, welche Gleichung die optimale Lösung erfüllen muss, damit das Funktional auch zu einem späteren Zeitpunkt optimal bleibt. Aus dieser Überlegung entsteht die Hamilton-Jacobi-Bellman-Gleichung. Das Problem kann dadurch in einzelne Zeitschritte aufgeteilt werden, anstatt es vollständig auf einmal zu lösen.

In der Physik war ein entsprechendes Prinzip schon länger bekannt, allerdings nicht unter dem Namen dynamische Programmierung. Der Übergang von einer globalen Betrachtungsweise, bei der alle Zeitpunkte gleichzeitig berücksichtigt werden, zu einer zeitabhängigen oder dynamischen Betrachtungsweise entspricht dort der Transformation der Lagrange-Funktion in die Hamilton-Funktion mithilfe der Legendre-Transformation.

Fibonacci-Zahlen als Musterbeispiel

Die Berechnung der n-ten Fibonacci-Zahl zeigt, wie dynamische Programmierung die Zeitkomplexität eines Verfahrens drastisch verbessern kann.

Eine naive rekursive Implementierung lautet sinngemäß:

• Falls n ≤ 1 gilt, wird n zurückgegeben.
• Andernfalls wird fib(n − 1) + fib(n − 2) berechnet.

Bei fib(4) entsteht ein Aufrufbaum, in dem fib(2) doppelt berechnet wird. Bei größeren Fibonacci-Zahlen nimmt die Zahl der mehrfachen Berechnungen exponentiell zu. Deshalb besitzt dieses naive Programm eine exponentielle Laufzeit.

Ein dynamisches Programm berechnet dagegen zunächst die kleineren Fibonacci-Zahlen und baut daraus die größeren auf. Für n = 0 wird 0 zurückgegeben. Andernfalls werden die Variablen previousFib := 0 und currentFib := 1 verwendet. In einer Schleife, die n − 1-mal wiederholt wird und bei n = 1 übersprungen wird, werden jeweils die nächsten Werte als Summe der beiden vorherigen berechnet und gespeichert.

Jede benötigte Berechnung wird dabei nur einmal durchgeführt. Die Laufzeit dieses Programms beträgt daher O(n).

Weitere algorithmische Anwendungen

Weitere im Artikel genannte Beispiele für Algorithmen oder Probleme, bei denen dynamische Programmierung eingesetzt wird, sind:

• CYK-Algorithmus
• Earley-Algorithmus
• Needleman-Wunsch-Algorithmus
• Smith-Waterman-Algorithmus
• Viterbi-Algorithmus
• Algorithmus von Floyd und Warshall
• pseudopolynomieller Algorithmus für das Rucksackproblem
• Berechnung der Levenshtein-Distanz