Practise › Questions › Dynamic programming
Dynamic programming questions
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.
6 original questions · 23 marks · the dynamic programming notes · Decision Mathematics 2
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
State Bellman's principle of optimality and say what it allows you to do.
Worked answer
Any part of an optimal path is itself optimal between its own two ends. It allows the problem to be solved backwards: once the best value from every vertex onwards is known, the best value at the vertex before it is one comparison away, and no route already rejected needs reconsidering. B1 for the principle, B1 for working backwards.From a vertex there are two options: a step of 6 to a vertex worth 11, and a step of 10 to one worth 5. Give the value of the vertex for a minimum-total problem and for a minimax problem.
Worked answer
Minimum total: min(6 + 11, 10 + 5) = min(17, 15) = 15, through the second option.
Minimax: min(max(6, 11), max(10, 5)) = min(11, 10) = 10, also through the second, but chosen because its worst single stage is smaller rather than because its total is. M1 for adding along each option, A1 for 15, B1 for 10 under the minimax rule.A network runs S to {A, B} to {C, D} to T with SA 5, SB 3, AC 4, AD 9, BC 8, BD 2, CT 6, DT 7. Find the shortest route from S to T by dynamic programming, setting your work out as a table.
Worked answer
Work backwards, one row per stage, state, action and value.
Stage 3 (state, action, value): C, CT, 6; D, DT, 7.
Stage 2: A, AC, 4 + 6 = 10*; A, AD, 9 + 7 = 16; so A is worth 10 through C. B, BC, 8 + 6 = 14; B, BD, 2 + 7 = 9*; so B is worth 9 through D.
Stage 1: S, SA, 5 + 10 = 15; S, SB, 3 + 9 = 12*; so S is worth 12 through B.
Reading the starred actions forwards gives the route S, B, D, T of length 12. M1 for working backwards in stages, A1 for the final stage values, M1 for the middle stage, A1 for its two values, A1 for the value at S, A1 for the route. Checking all four routes gives 12, 15, 17 and 21, confirming it. Marks are for the table itself, so every option must appear, not only the winner.In that solution the step from S to B costs 3 while S to A costs 5, and B also won. Explain why this does not show that taking the cheapest first step is a sound method.
Worked answer
The two happen to agree here, which is exactly why the example is a poor test of the method. The choice was made by comparing 5 + 10 with 3 + 9, both of which use values found from the far end. Had the value at A been 5 rather than 10, S to A would have won at 10 despite the dearer first step. A greedy first move carries no guarantee about what follows it. B1 for the comparison using values from the far end, B1 for the altered example, B1 for a greedy first step giving no guarantee.Explain the difference between the stage variable and the state variable, using the network above.
Worked answer
The stage says how far through the process you are: here there are three stages, one per arc travelled. The state says where you are within that stage. At stage 2 the states are A and B, and at stage 3 they are C and D. B1 for the stage, B1 for the state, B1 for the states named in this network. Every row of the table is one stage and state pair together with one action, and naming all three is part of the answer.For the same network, find the route whose smallest single stage is as large as possible, and state that largest value.
Worked answer
This is a maximin problem, so the addition is replaced by taking the minimum along a route.
Stage 3: C is worth 6 and D is worth 7, as before.
Stage 2: A gives max(min(4, 6), min(9, 7)) = max(4, 7) = 7 through D; B gives max(min(8, 6), min(2, 7)) = max(6, 2) = 6 through C.
Stage 1: S gives max(min(5, 7), min(3, 6)) = max(5, 3) = 5 through A.
The route is S, A, D, T with smallest stage 5. B1 for replacing addition by the minimum along a route, M1 for the middle stage, A1 for its two values, M1 for the first stage, A1 for the value 5, A1 for the route. It is a different route from the shortest one, which shows that the two objectives genuinely pull apart: S, A, D, T is the longest route of the four by total length, at 21.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise dynamic programming one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.