Dynamische Programmierung

Dynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematische Speicherung von Zwischenresultaten. Der Begriff wurde in den 1940er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt, der diese Methode auf dem Gebiet der Regelungstheorie anwandte. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen.

Dynamische Programmierung kann erfolgreich eingesetzt werden, wenn ein Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt. Dies nennt man Optimalitätsprinzip von Bellman. In der dynamischen Programmierung werden zuerst die optimalen Lösungen der kleinsten Teilprobleme direkt berechnet und dann geeignet zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt. Dieses Verfahren setzt man fort, bis das ursprüngliche Problem gelöst wurde. Einmal berechnete Teilergebnisse werden in einer Tabelle gespeichert. Bei nachfolgenden Berechnungen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt sie jedes Mal neu zu berechnen, was zu einer Senkung der Laufzeit führt. Wird die dynamische Programmierung konsequent eingesetzt, vermeidet sie kostspielige Rekursionen, weil bekannte Teilergebnisse wiederverwendet werden.

In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert der Zielfunktion zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das Funktional auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur Hamilton-Jacobi-Bellman-Gleichung. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen.

In der Physik war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation der Lagrange-Funktion in die Hamilton-Funktion mit Hilfe der Legendre-Transformation.

Musterbeispiel

Durch die Nutzung von dynamischer Programmierung kann die Zeitkomplexität zur Berechnung der n-ten Fibonacci-Zahl drastisch verbessert werden.

Eine naive Implementation wäre:

function fib(n)
    if n <= 1 return n
    return fib(n − 1) + fib(n − 2)

Ein Aufruf von fib(4) zur Berechnung der vierten Fibonacci-Zahl erstellt folgenden Aufrufbaum:

fib(4)
fib(3) + fib(2)
(fib(2) + fib(1)) + fib(2)
((fib(1)+fib(0)) + fib(1)) + fib(2)
((fib(1)+fib(0)) + fib(1)) + (fib(1) + fib(0))

Die Berechnung für fib(2) wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.

In einem möglichen dynamischen Programm berechnen wir erst die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
        return currentFib

Da wir jede Berechnung nur einmal durchführen, hat dieses Programm eine Laufzeit von O(n).

Weitere Beispiele

CYK-Algorithmus
Earley-Algorithmus
Needleman-Wunsch-Algorithmus
Smith-Waterman-Algorithmus
Viterbi-Algorithmus
Algorithmus von Floyd und Warshall
Pseudopolynomieller Algorithmus für das Rucksackproblem^[1]
Berechnung der Levenshtein-Distanz

Siehe auch

Literatur

Richard Bellman: Dynamic Programming. Princeton University Press, 1957.
Stuart Dreyfus: Richard Bellman on the birth of Dynamic Programming. Band 50, Nr. 1, 2002, S. 48–51 (informs.org [PDF]).
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 323–369 (englisch).

Weblinks

ADP an der Uni Bielefeld

Einzelnachweise

↑ Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin / Heidelberg 2008, ISBN 978-3-540-77977-3, S. 243–246, doi:10.1007/978-3-540-77978-0.

[1] Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin / Heidelberg 2008, ISBN 978-3-540-77977-3, S. 243–246, doi:10.1007/978-3-540-77978-0.

[1]