Dynamic programming

Explanation

• Dynamic programming solves a multi-stage decision problem by working backwards from the finish. Bellman's principle of optimality states that any part of an optimal path is itself optimal: if the best route from $S$ to $T$ passes through a vertex $V$, then the part of it from $V$ to $T$ must be the best route from $V$ to $T$.
• That is what makes the backward calculation valid, because the best value from each vertex can be computed once and then reused. Two kinds of variable organise the work.
• The stage variable says how far through the process a decision is being made, for example which column of the network or which month of a production plan. The state variable says which situation the process is in at that stage, for example which vertex of that column or how much stock is held.
• The tabulation lists, for every stage and state, the possible actions, the value of each action and the best of them, and the optimal value is read from the final row. The same table solves four kinds of problem: maximum and minimum total, where actions are added to the value already found;
• minimax, where the value of a route is its largest arc and the aim is to make that as small as possible; and maximin, where the value is its smallest arc and the aim is to make that as large as possible.