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.

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₁ + + z₂) = h(h(z₁) + + h(z₂))

(Giegerich et. al., 2002)

$z_i, 1\le i\le 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.
• Thomas L. Morin: Monotonicity and the Principle of Optimality. In: Journal of mathematical analysis and applications. 86, 1982, S. 665-674.
• 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 (http://bibiserv.techfak.uni-bielefeld.de/adp/ps/adp_discipline.pdf 260 KB).