Dynamisches Programmieren

Dynamisches Programmieren ist eine algorithmische Methode zum Lösen von Optimierungsproblemen. Der Begriff wurde in den 1940er Jahren von dem amerikanischen Mathematiker Richard Bellman geprägt, der diese Methode auf dem Gebiet der Kontrolltheorie anwendete. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen.

Dynamisches Programmieren kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht, und eine optimale Lösung des Problem sich aus optimalen Lösungen der Teilproblemen zusammensetzt. Die Methode des dynamischen Programmiernens besteht darin, zuerst die optimalen Lösungen der kleinsten Teilprobleme zu berechen, und diese dann geeignet zu einer Lösung eines nächstgrößeren Teilproblem zusammensetzt und so weiter.

In der Kontrolltheorie und verwandten Gebieten kann man das Prinzip des dynamischen Programmierens einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman Gleichung), dessen 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 muss die optimale Lösung erfüllen, 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-Funktional in das Hamilton-Funktional mit Hilfe der Legendretransformation.

• Beispiel: CYK-Algorithmus