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)

Gemeint ist:

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,\dots ,x_k)|x_1\leftarrow z_1,\dots ,x_k\leftarrow z_k])=h([f(x_1,\dots ,x_k)|x_1\leftarrow h(z_1),\dots ,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\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

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur