Optimalitätsprinzip von Bellman

Das Optimalitätsprinzip von Bellman ist ein grundlegendes Prinzip der Optimierung. Es ist nach Richard Bellman benannt und besagt, dass sich bei einigen Optimierungsproblemen jede Optimallösung aus optimalen Teillösungen zusammensetzt. Auf diesem Prinzip basieren Algorithmen der dynamischen Programmierung.

Ein Beispiel ist die Berechnung eines kürzesten Weges in einem Graphen (z. B. einem Straßennetz). Ein kürzester Weg P zwischen den Knoten (Städten) A und B, der durch die Knoten X und Y führt, muss auch zwischen X und Y einen kürzesten Weg zwischen diesen beiden Knoten verwenden. Wäre das nicht der Fall, könnte P verkürzt werden, indem zwischen X und Y ein kürzerer Teilweg verwendet wird, und dann wäre P kein kürzester Weg zwischen A und B gewesen, im Widerspruch zur Annahme. Der Bellman-Ford-Algorithmus zur Berechnung kürzester Wege, der auf dynamischer Programmierung beruht, macht sich dieses Prinzip zunutze. Dargestellt werden solche Graphen in einem Quelle-Senken-Baum.

Definition (Klassisch)

„An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.“

– Bellman, 1957

„Eine optimale Entscheidungsfolge hat die Eigenschaft, dass, wie auch immer der Anfangszustand war und die erste Entscheidung ausfiel, die verbleibenden Entscheidungen eine optimale Entscheidungsfolge bilden müssen, bezogen auf den Zustand, der aus der ersten Entscheidung resultiert.“

Gemeint ist:

„Eine optimale Entscheidungsfolge hat die Eigenschaft, dass, wie auch immer der Anfangszustand war und die erste Entscheidung ausfiel, die verbleibenden Entscheidungen ebenfalls eine optimale Entscheidungsfolge bilden müssen, betrachtet über alle möglichen Entscheidungsfolgen, deren Anfang bei dem Zustand liegt, der aus der ersten Entscheidung resultiert.“

Definition (Formal)

Sei $h$ eine Optimierungsfunktion, welche auf Listen arbeitet, dann gilt das Optimalitätsprinzip von Bellman für eine $k$-stellige Funktion $f$, wenn gilt:

• $h([f(x_{1},\ldots ,x_{k})|x_{1}\leftarrow z_{1},\ldots ,x_{k}\leftarrow z_{k}])=h([f(x_{1},\ldots ,x_{k})|x_{1}\leftarrow h(z_{1}),\ldots ,x_{k}\leftarrow h(z_{k})])$
• $h(z_{1}{++}z_{2})=h(h(z_{1}){++}h(z_{2}))$

(Giegerich et al., 2002)

$z_{i},1\leq i\leq k$ sind Listen vom Typ $A$. $h$ ist vom Typ $h::[A]->[A]$. Der $++$ ist der Listenverknüpfungsoperator und $[|]$ ist die Listenbeschreibungs-Notation, wie sie in Haskell definiert sind.

Literatur

• Richard Bellman: Dynamic Programming. Princeton University Press, 1957 (englisch). 
• Thomas L. Morin: Monotonicity and the Principle of Optimality. In: Journal of Mathematical Analysis and Applications. Band 86, 1982, S. 665–674 (englisch). 
• R. Giegerich, C. Meyer, P. Steffen: Towards a Discipline of Dynamic Programming. In: GI Edition - Lecture Notes in Informatics. Bonner Köllen Verlag, 2002, S. 3–44 (englisch, uni-bielefeld.de [PDF; 260 kB]).