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.
WHAT YOU PROBABLY THINK
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 passes through a particular vertex, the part from that vertex onwards must be the best route from there.
That licenses working backwards. Find the best value from each vertex in the last stage, then the stage before, each time choosing the best of a few options whose continuations are already known. Working forwards and taking the cheapest step, as the opening claim describes, is a greedy walk with no such guarantee: it is 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; 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. Note that C has the best onward value but the worst total.
Tabulation, and other objectives
Written as a table, each row gives a state, the options available from it, and the best value found. The rows for the final stage are filled first, and later rows quote values already in the table rather than recomputing them. Both the network and the table format are examinable, and the table is the more reliable when the network is 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 is unchanged: replace the addition with taking a maximum or a minimum along the route, and choose between options in the usual way.
YOUR TURN
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 S, B, E, T again, but chosen for a different reason and with a different value.
THE EXAM BIT
- Name the stage and state variables before filling anything in.
- Work strictly backwards and quote values already found rather than 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.
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
M
i
n
i
m
u
m
t
o
t
a
l
:
m
i
n
(
5
+
9
,
8
+
4
)
=
1
2
,
t
h
r
o
u
g
h
t
h
e
s
e
c
o
n
d
.
M
i
n
i
m
a
x
:
m
i
n
(
m
a
x
(
5
,
9
)
,
m
a
x
(
8
,
4
)
)
=
m
i
n
(
9
,
8
)
=
8
,
a
l
s
o
t
h
r
o
u
g
h
t
h
e
s
e
c
o
n
d
,
b
u
t
f
o
r
a
d
i
f
f
e
r
e
n
t
r
e
a
s
o
n
.
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 minimum.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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.
No animated video for this topic yet; these notes stand alone.