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.
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.
Weblinks
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.
