Questions on dynamic programming and Bellman's principle

Question 1

State Bellman's principle of optimality and say what it allows you to do.

Accepted 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.

Question 2

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.

Accepted 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.

Question 3

A completed table records the best action at each state as: at S go to C, at A go to E, at B go to D, at C go to E, at D go to T and at E go to T. Write down the optimal route from S to T.

Accepted Answer

The table was built backwards, so the route is read forwards: start at S, take the action recorded there, and repeat at whatever state it leads to. M1 for following the recorded actions forwards from S. S sends you to C, C sends you to E, E sends you to T, so the route is S, C, E, T. A1. The rows for A, B and D are the options the table rejected on the way, and no route needs to visit them.

Question 4

State the four things recorded in each row of a dynamic programming table.

Accepted Answer

The stage, which says how far through the process the row belongs; the state, which says where you are within that stage; the action, which is one of the choices available from that state; and the value of that action, formed from the action's own contribution and the value already found for wherever it leads. B1 for stage and state, B1 for action and value. The best of the values against one state is then marked, and it is that mark which is read forwards at the end to give the route.

Question 5

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.

Accepted 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. Every option must appear in the table, not only the winner.

Question 6

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.

Accepted 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.

Question 7

Explain the difference between the stage variable and the state variable, using the network above.

Accepted 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.

Question 8

A network runs S to {P, Q} to {U, V} to {W, X} to T with SP 3, SQ 5, PU 6, PV 2, QU 4, QV 7, UW 5, UX 8, VW 3, VX 4, WT 6 and XT 2. A student's table records the values U 10, V 9, P 11, Q 14 and S 14, and reports the shortest route as S, P, V, W, T of length 14. One value has been worked out wrongly and every later value follows correctly from it. Identify the wrong value, correct it, rework the table, and give the shortest route and its length.

Accepted Answer

At the last stage W is worth 6 and X is worth 2. At the stage before, U gives min(5 + 6, 8 + 2) = 10 through X, which the student has right, but V gives min(3 + 6, 4 + 2) = 6 through X, not the 9 recorded. M1 for recomputing that stage, A1 for V being 6 through X.
Every later row followed correctly from the wrong number, which is why only one value is wrong and the rest of the table still looks consistent. Correcting it: P gives min(6 + 10, 2 + 6) = 8 through V, Q gives min(4 + 10, 7 + 6) = 13 through V, and S gives min(3 + 8, 5 + 13) = 11 through P. M1 for reworking the later stages, A1 for 8, 13 and 11.
Reading the actions forwards, the shortest route is S, P, V, X, T, of length 3 + 2 + 4 + 2 = 11. A1.
The student's route was 14 long, so the single slip at V put the answer three units high and sent the route through W instead of X.

Question 9

In a dynamic programming table the number recorded against a state is the best result obtainable from that state onwards. Explain why one number for each state is enough, whatever route was taken to reach it, and say what the table would have to hold if that were not so.

Accepted Answer

The arcs leaving a state, and what each of them contributes, depend on the state alone and not on how it was arrived at, so the best result from there onwards is a property of the state. B1.
Bellman's principle then says that the continuation of an optimal route from that state is itself optimal, so a route arriving there can be valued by adding its own cost so far to that one number: no earlier detail is needed again. B1.
If the onward value did depend on the route taken, one number per state would not describe the continuation and the table would need a row for every partial route rather than for every state, which is the enumeration the method exists to avoid. B1.

Question 10

A haulier drives from a depot S to a site T through a network running S to {P, Q, R} to {U, V} to T. Each road carries a weight limit in tonnes: SP 18, SQ 24, SR 17, PU 20, PV 15, QU 12, QV 26, RU 14, RV 22, UT 22 and VT 19. A lorry can use a route only if it is within every limit along it. Find the route that allows the heaviest lorry, and state that weight.

Accepted Answer

A route is worth the smallest limit along it, and the haulier wants that smallest limit as large as possible, so this is a maximin problem: replace the addition by taking the minimum along the route, and still take the best of the options at each state. B1 for the objective identified.
Last stage: U is worth 22 and V is worth 19, each having one road left.
Middle stage: P gives max(min(20, 22), min(15, 19)) = max(20, 15) = 20 through U; Q gives max(min(12, 22), min(26, 19)) = max(12, 19) = 19 through V; R gives max(min(14, 22), min(22, 19)) = max(14, 19) = 19 through V. M1 for the middle stage, A1 for 20, 19 and 19.
At S: max(min(18, 20), min(24, 19), min(17, 19)) = max(18, 19, 17) = 19 through Q. M1 for the first stage, A1 for the route S, Q, V, T carrying 19 tonnes.
Checking the six routes directly gives limits 18, 15, 12, 19, 14 and 17, so 19 is right and is reached by that route alone. P has the best onward value of the three, and still loses at S, because the road into it is the lighter one.

Question 11

A network runs S to {J, K, L} to {G, H} to T with SJ 5, SK 3, SL 4, JG 4, JH 9, KG 8, KH 5, LG 2, LH 7, GT 6 and HT 4. Find the length of the shortest route, state every route of that length, and say how the table shows that there is more than one.

Accepted Answer

Last stage: G is worth 6 and H is worth 4.
Middle stage: J gives min(4 + 6, 9 + 4) = 10 through G; K gives min(8 + 6, 5 + 4) = 9 through H; L gives min(2 + 6, 7 + 4) = 8 through G. M1 for working backwards, A1 for 10, 9 and 8.
At S: min(5 + 10, 3 + 9, 4 + 8) = min(15, 12, 12) = 12, and the smallest value is reached by two of the three options, so both are marked in the table rather than one. A1 for 12 with both actions marked.
Reading each of them forwards gives S, K, H, T and S, L, G, T, of lengths 3 + 5 + 4 and 4 + 2 + 6, both 12. A1 for both routes.
A tie is not an error and does not have to be broken: either route may be quoted so long as the working says both are shortest.

Question 12

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 route whose smallest single stage is as large as possible, and state that largest value.

Accepted 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, each having one arc left. 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: S, A, D, T is the longest route of the four by total length, at 21.

Question 13

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 route whose largest single stage is as small as possible, and state that value.

Accepted Answer

This is a minimax problem: the value of a route is its largest single stage, so the addition is replaced by taking the maximum along a route. Stage 3: C is worth 6 and D is worth 7, each having one arc left. Stage 2: A gives min(max(4, 6), max(9, 7)) = min(6, 9) = 6 through C; B gives min(max(8, 6), max(2, 7)) = min(8, 7) = 7 through D. Stage 1: S gives min(max(5, 6), max(3, 7)) = min(6, 7) = 6 through A. The route is S, A, C, T, whose largest stage is 6. B1 for replacing the addition by the maximum along a route, M1 for the middle stage, A1 for 6 and 7, A1 for the value 6 at S, A1 for the route. Checking directly, the four routes have largest stages 6, 9, 8 and 7. The three objectives solved on this network give three different routes: shortest S, B, D, T; maximin S, A, D, T; minimax S, A, C, T.

Question 14

Each arc of a network earns a profit. From S, the arc to A earns 4, to B earns 6 and to C earns 3; then AD earns 5, AE 8, BD 4, BE 2, CD 9 and CE 7; finally DT earns 5 and ET 6. Use dynamic programming to find the route from S to T of greatest total profit.

Accepted Answer

The objective is a maximum, so each state takes the largest of its options instead of the smallest, and everything else is unchanged. Stage 3: D is worth 5 and E is worth 6. Stage 2: A gives max(5 + 5, 8 + 6) = 14 through E; B gives max(4 + 5, 2 + 6) = 9 through D; C gives max(9 + 5, 7 + 6) = 14 through D. Stage 1: S gives max(4 + 14, 6 + 9, 3 + 14) = max(18, 15, 17) = 18 through A. The route is S, A, E, T with profit 18. B1 for maximising at each state, M1 for the middle stage, A1 for 14, 9 and 14, M1 for the stage at S, A1 for 18, A1 for the route. A greedy forward walk takes the 6 to B and can then earn no more than 15 in total, and C matches A's onward value of 14 yet loses at S: the comparison of 4 + 14 with 3 + 14 is decided by the first arc, which only the backwards working weighs correctly.

Question 15

A staged network runs from S through three successive stages of four vertices each to T, and every vertex is joined to every vertex of the next stage. State the number of routes from S to T, and explain why dynamic programming finds the best one without evaluating every route separately.

Accepted Answer

A route chooses one vertex in each of the three stages, so there are 4 × 4 × 4 = 64 routes. Dynamic programming instead examines each arc once: by Bellman's principle any part of an optimal route is itself optimal, so each vertex needs only its single best onward value, found once and then reused by every route through that vertex rather than recomputed for each of them. The network has 4 + 16 + 16 + 4 = 40 arcs, so 40 comparisons of an arc with a value already found replace 64 separate route totals. B1 for 64, B1 for Bellman's principle and the reuse of each vertex's best value, M1 for counting the arcs, A1 for 40 and the comparison. Add a fourth stage of four and the routes multiply to 256 while the arcs grow only to 56.