- Dynamische Programmierung
-
Dynamische Programmierung ist eine Methode zum algorithmischen Lösen von Optimierungsproblemen. Der Begriff wurde in den 1940er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt, der diese Methode auf dem Gebiet der Regelungstheorie anwendete. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen.
Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt (Optimalitätsprinzip von Bellman). Das Verfahren der dynamischen Programmierung besteht darin, zuerst die optimalen Lösungen der kleinsten Teilprobleme direkt zu berechnen, und diese dann geeignet zu einer Lösung eines nächstgrößeren Teilproblems zusammenzusetzen, und so weiter. 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. 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 des Zielfunktionals zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das Zielfunktional 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 des Lagrange-Funktionals in das Hamilton-Funktional mit Hilfe der Legendre-Transformation.
Inhaltsverzeichnis
Beispiele
- CYK-Algorithmus
- Earley-Algorithmus
- Needleman-Wunsch-Algorithmus
- Smith-Waterman-Algorithmus
- Viterbi-Algorithmus
- Algorithmus von Floyd und Warshall
- Pseudopolynomieller Algorithmus für das Rucksackproblem
Siehe auch
Literatur
- Richard Bellman: Dynamic Programming. Princeton University Press, 1957.
- Stuart Dreyfus: Richard Bellman on the birth of Dynamic Programming. 50, Nr. 1, 2002, S. 48–51 (http://www.eng.tau.ac.il/~ami/cd/or50/1526-5463-2002-50-01-0048.pdf).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7, S. 323–369.
Weblinks
Wikimedia Foundation.
