Maths › Decision Mathematics 2 › Dynamic programming
Dynamic programming
Work backwards from the end. Any part of an optimal route is itself optimal, so once you know the best from every point onwards, one comparison at each stage finishes the job.
Builds on Shortest paths: Dijkstra and Floyd and Critical path analysis.
IN THIS TOPIC
- State Bellman's principle of optimality and explain what it licenses.
- Set out a solution as a table with stage and state variables.
- Handle minimax and maximin objectives as well as totals.
COMMON MISCONCEPTION
Dynamic programming works forwards from the source, choosing the cheapest step available at each stage.
Backwards, because of Bellman
Bellman's principle of optimality says that any part of an optimal path is itself optimal between its own two ends. So if the best route from the source happens to pass through a particular vertex, the part from that vertex onwards must be the best route from there.
That is what licenses working backwards. Find the best value from each vertex in the last stage, then the stage before, each time choosing between a few options whose continuations you already know. Work forwards taking the cheapest step instead, and you have a greedy walk with no such guarantee, the same mistake as confusing Dijkstra with nearest neighbour.
Two variables organise the work. The stage says how far through the process you are; the state says which vertex you are at within that stage. Every question uses both, and setting them out explicitly is what the marks are for.
WORKED EXAMPLE
Backwards through three stages
From S the options are A (4), B (2), C (5). From A: D (3), E (6). From B: D (5), E (4). From C: D (6), E (2). From D: T (7). From E: T (4). Find the shortest route.
Last stage: from D the value is 7, from E it is 4.
Stage 2: A gives min(3 + 7, 6 + 4) = 10, a tie between the two routes; B gives min(5 + 7, 4 + 4) = 8 through E; C gives min(6 + 7, 2 + 4) = 6 through E.
Stage 1: S gives min(4 + 10, 2 + 8, 5 + 6) = 10 through B.
The route is S, B, E, T of length 10. C has the best onward value of the three, yet it loses to B, because the extra 3 it costs to reach C outweighs the 2 it saves later.
Tabulation, and other objectives
Written as a table, each row gives a state, the options available from it, and the best value found. Fill the rows for the final stage first, and let later rows quote values already in the table instead of recomputing them. Both the network and the table are examinable, and the table is the more reliable once the network gets large.
Not every problem adds. A minimax problem wants the route whose largest single step is as small as possible, which is what you want when the worst stretch is what matters. A maximin problem wants the largest possible smallest step. The method does not change. Replace the addition by taking a maximum or a minimum along the route, and choose between the options in the usual way.
GUIDED PRACTICE
A minimax reading
Explain how the working changes if the question asks for the route whose longest single stage is as small as possible.
Show the working
At the last stage the value at each vertex is still the length of its only remaining step: D 7, E 4.
At stage 2 the value of an option is the larger of its own step and the value beyond: A gives min(max(3,7), max(6,4)) = 6 through E.
Similarly B gives min(max(5,7), max(4,4)) = 4 and C gives min(max(6,7), max(2,4)) = 4.
At S: min(max(4,6), max(2,4), max(5,4)) = 4, through B. The route is S, B, E, T again, chosen for a different reason and reported with a different value.
ASSESSMENT FOCUS
- Name the stage and state variables before filling anything in.
- Work strictly backwards and quote values already found instead of recomputing them.
- Set the working out as a table with an options column and a best column.
- For minimax or maximin, replace the addition with a maximum or minimum and say that you have.
- Read the route off by following the choices forwards once the table is complete, and state it in order.
CHECK YOURSELF
From a vertex the options are a step of 5 to a vertex worth 9, and a step of 8 to one worth 4. Give the value of this vertex for a minimum-total problem and for a minimax problem.
Show a hint
Add for one, take the larger for the other.
Show the answer
Minimum total: min(5 + 9, 8 + 4) = 12, through the second. Minimax: min(max(5, 9), max(8, 4)) = min(9, 8) = 8, also through the second, but for a different reason.
Bellman's principle says any part of an optimal path is optimal, which licenses working backwards from the end.
Tabulate stage against state, quoting values already found.
For minimax or maximin replace the addition with a maximum or a minimum along the route.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the dynamic programming questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- State Bellman's principle of optimality and explain what it licenses.
- Set out a solution as a table with stage and state variables.
- Handle minimax and maximin objectives as well as totals.
Open the full revision checklist to see every objective in the course in one place.