Optimalitätsprinzip von Bellman

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

Bellman-Gleichung

Einfache Sprache

Die Bellman-Gleichung besagt, dass die Länge des kürzesten Weges zu einem Knoten $k$ das Minimum des der Länge des kürzesten Weges zu den angrenzenden Knoten unter Berücksichtungen derer individuellen Entfernung zu $k$.

Def. Bellman-Gleichung

Sei $u_i$ die Länge (Gewicht) des kürzesten Weges von dem Knoten $0$ zu dem Knoten $i$. $a_{ij}$ ist die

$$u_1 = 0$$

$$u_j = \min_{k\not=j}[u_k+a_{kj}]$$

Wenn der Graph keinen gerichteten Kreis negativer Länge besitzt (d.h. die minimale Zyklus-Länge $ZL\geq 0$), ist die Bellman-Gleichung notwendig aber nicht hinreichend für den kürzesten Weg. Sonst könnte man die Kreise unendlich oft durchlaufen, um die Länge zu verringern.