Dynamic programmingEdexcel A-Level Further Maths: Revision notes

Dynamic programming solves a problem by splitting it into stages, solving the last stage first and working backwards. At each stage the state variable describes where you are (for example, the vertex, or the number of units left), and the action is the decision made there (for example, the next vertex, or how many units to use). Bellman's principle of optimality: any part of an optimal route is itself optimal. For example, any part of the shortest (or longest) route from source to sink is itself a shortest (or longest) route between its end points. So the best way onward from a state does not depend on how you reached it, and we can store one best value for each state.

Work backwards from the sink. For each state, the value is the minimum over the actions of (arc length $+$ value of the next state). Record each stage in a table with columns stage, state, action, value, then read the route forwards from the start. Example: arcs SA 6, SB 5, AC 3, AD 8, BC 5, BD 4, CT 7, DT 3. Stage 1: C $7$, D $3$. Stage 2: A $=\min(3+7,\,8+3)=10$ via C; B $=\min(5+7,\,4+3)=7$ via D. Stage 3: S $=\min(6+10,\,5+7)=12$ via B. Shortest route S, B, D, T, length $12$.

The same method works with other ways of combining arcs.

• Maximum route (longest, or greatest profit): value $=\max(\text{arc}+\text{next value})$.
• Minimax route: the largest arc used is as small as possible. Value $=\min\big(\max(\text{arc},\,\text{next value})\big)$.
• Maximin route: the smallest arc used is as large as possible. Value $=\max\big(\min(\text{arc},\,\text{next value})\big)$. Example (minimax, same network as above): C $7$, D $3$; A $=\min(\max(3,7),\max(8,3))=7$ via C; B $=\min(\max(5,7),\max(4,3))=4$ via D; S $=\min(\max(6,7),\max(5,4))=5$ via B. The route S, B, D, T has largest arc $5$.

Dynamic programming is not only for networks. To share $N$ units between several activities, take the activities one at a time. The stage is the number of activities considered so far, the state is the number of units available, and the action is the number given to the current activity. Stage 1 is the last activity, which takes all the units left. For later stages the value of a state $s$ is $\max_k\big(\text{profit}(k)+\text{value of the previous stage with }s-k\text{ units}\big)$. Example with three projects and 4 engineers: if Project 3 gives $18$ for 4 engineers and $14$ for 3, and Project 2 gives $6$ for 1 engineer, then giving 1 engineer to Project 2 with 4 available gives $6+14=20$. The final stage gives the best total, and the actions are read back to give the allocation.

1. State the stages and what state and action mean.
2. Work backwards: complete each stage's table before the next.
3. For each state, list every action and its total so that a marker can see the minimum, maximum, minimax or maximin chosen.
4. At the first stage, read the answer, then trace the actions forwards to give the route or allocation.
5. Quote the final answer in the units of the question.