Dynamic programming
Studying this course? Keep your progress in one place.
Key facts
- Dynamic programming splits a problem into stages and works backwards from the last.
- The state says where you are; the action is the decision made there.
- Bellman's principle: any part of an optimal route is itself optimal.
- For a minimum route, value . Minimax and maximin use the larger or smaller of arc and next value.
- Complete each stage's table before the next, then read the route forwards.
Stages, states and Bellman
Split the problem into stages, solve the last first and work backwards. Bellman's principle lets you store one best value per state.
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 (the vertex, or the number of units left), and the action is the decision (the next vertex, or how many units to use).
So the best way onward from a state does not depend on how you reached it, and one best value is stored for each state.
- Bellman's principleany part of an optimal route is itself optimal
What does Bellman's principle let us do?
A minimum route
Work backwards from the sink. Each state's value is the minimum over actions of arc length plus next value.
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.
State which way you number the stages, work back one stage at a time, and only then read the route forwards.
Worked example
Arcs: 6, 5, 3, 8, 5, 4, 7, 3. Find the shortest route from to .
- 1
Stage 1: , .
- 2
Stage 2: via ; via .
- 3
Stage 3: via .
- 4
Read forwards: , then , then , then .
A state has an arc of length 4 to a state of value 9, and an arc of 6 to a state of value 5. What is its minimum value?
Maximum, minimax and maximin
Maximum uses max of arc plus next. Minimax uses the larger of arc and next, then the minimum. Maximin uses the smaller, then the maximum.
The same method works with other ways of combining arcs.
- Maximum route (longest, or greatest profit): value .
- Minimax route: the largest arc used is as small as possible.
- Maximin route: the smallest arc used is as large as possible.
In minimax and maximin problems do not add the arc and the next value: take the larger (minimax) or the smaller (maximin) of the two.
| Maximum | Minimax | Maximin | |
|---|---|---|---|
| Aim | Greatest total | Largest arc as small as possible | Smallest arc as large as possible |
| Value |
Maximum
- Aim:
- Greatest total
- Value:
Minimax
- Aim:
- Largest arc as small as possible
- Value:
Maximin
- Aim:
- Smallest arc as large as possible
- Value:
Worked example
Use the same network. Find the route whose largest arc is as small as possible.
- 1
Stage 1: , .
- 2
via .
- 3
via .
- 4
via .
In a maximin problem, an arc of 6 leads to a state of value 4. What is the value through that arc?
Allocation problems
Take the activities one at a time: stage is activities considered, state is units available, action is units given to the current activity.
Dynamic programming is not only for networks. To share units between several activities, take the activities one at a time.
Stage 1 is the last activity, which takes all the units left. For later stages the value of a state is .
Keep the columns in the order stage, state, action, value so that each line can be checked from the previous stage.
- 1
Stage 1: the last activity
takes all the units left in each state
- 2
Stage 2: add the next activity
try every action k and add its profit to the stage 1 value for s − k units
- 3
Record the best value for each state
and the action that gave it
- 4
Work back to the full N units
read off the best total, then trace the actions
Stage
- Activities considered so far
State
- Units available
Action
- Units given to the current activity
Value
- Best total profit from here onwards
Worked example
Three projects and 4 engineers. Project 3 gives 18 for 4 engineers and 14 for 3. Project 2 gives 6 for 1 engineer. What is the value of giving 1 engineer to Project 2 when 4 are available?
- 1
Giving 1 engineer to Project 2 leaves for the earlier stage.
- 2
That stage gives 14 for 3 engineers.
- 3
Total .
With 5 units available, you give 2 to the current activity. How many units does the previous stage have?
Setting out a solution
Define the stages, complete each table before the next, show every action, then trace the route forwards.
A clear layout earns the method marks.
Work backwards from the sink or last activity: complete each stage's table before the next. List each action and its total so a marker sees the minimum, maximum, minimax or maximin chosen.
At the first stage read off the best value, then trace the actions forwards. Quote the final answer in the units of the question.
- 1
Define
state the stages and what state and action mean
- 2
Work backwards
complete each stage's table before the next
- 3
Show every action
list each action and its total
- 4
Read the answer
at the first stage, then trace the actions forwards
- 5
Conclude
quote the final answer in the units of the question
In which order do you complete the stages?
Try an exam question
A network has arcs 4, 7, 6, 2, 3, 5, 5 and 8. Use dynamic programming to find the shortest route from to and its length.
[4 marks]
- [1]Works backwards from : and .
- [1] via ; via .
- [1] via .
- [1]The shortest route is with length 14.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Working backwards from T, what is the shortest distance from A to T?
1 mark, marked against the mark scheme
Working backwards from T, what is the shortest distance from A to T?
1 mark, marked against the mark scheme