Bellman equation

The optimality principle of Bellman is a fundamental principle of optimization. It is named after Richard Bellman and states that any optimal solution is composed with some optimization problems of optimal partial solutions. This is the principle of dynamic programming based algorithms.

One example is the calculation of a shortest path in a graph (such as a road network ). A shortest path P between the nodes ( cities) A and B, X and Y through the nodes must use a shortest path between these two nodes between x and y. Would not that be the case, P could be shortened by a shorter sub-path is used between X and Y, then P would not be a shortest path between A and B, contradicting the assumption. The Bellman - Ford algorithm for calculating shortest paths, which is based on dynamic programming, this principle makes use of.

Definition ( Classic )

"An optimal policy Has the property did whatever the initial state and initial decision are, the Remaining Decisions must Constitute of optimal policy with regard to the state Resulting from the first decision. "

" An optimal decision sequence has the property that, whatever was the initial state and the initial decision failed, the remaining decisions must constitute an optimal decision result, based on the state resulting from the first decision. "

What is meant is:

" An optimal decision sequence has the property that, whatever was the initial state and the initial decision failed, the remaining decisions must also form an optimal decision result, considered over all possible decision sequences whose beginning is the state resulting from the first decision results. "

Definition ( Formal)

Let h be an optimization function that operates on lists, then the optimality principle of Bellman for a k- ary function f is valid if:

( Giegerich et. Al., 2002)

Are lists of type. is of type. That is the list concatenation operator and the list description notation, as defined in Haskell.