Dynamic programming

Dynamic programming Test

Spec 4.1 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Dynamic programming

Total 27 marks

Name

Class

Date

  1. 1
    A network of roads joins S to T through junctions A, B, C and D. The roads and their lengths, in km, are: SA 5, SB 3, AC 4, AD 7, BC 6, BD 2, CT 5 and DT 6. Dynamic programming is used to find the shortest route from S to T, working backwards from T. Stage 1 is the final step into T (from C or D), stage 2 is the step from A or B, and stage 3 is the step from S. The state is the vertex and the action is the next vertex.
    (a)
    Working backwards from T, what is the shortest distance from A to T?
    [1 mark]
    • A1313 km
    • B1111 km
    • C99 km
    • D77 km
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Which statement is Bellman's principle of optimality?
    [1 mark]
    • AThe shortest route always begins with the shortest road leaving S
    • BThe best road at every junction is the shortest road leaving it
    • CA shortest route must pass through the same number of junctions as any other route
    • DAny part of a shortest route is itself a shortest route between its end points
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Given that the shortest distance from A to T is 99 km, complete the dynamic programming to find the shortest route from S to T and its length.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: shortest distance from B to T is min⁡(6+5, 2+6)=8\min(6+5,\,2+6)=8 via D
    B1: from S,
    min⁡(5+9, 3+8)=11\min(5+9,\,3+8)=11 via B; the shortest route is S, B, D, T of length 1111 km
    Accept: a table showing stage, state, action and value

    Total for question 1: 4 marks

  2. 2
    Messages are sent from S to T through routers A, B, C and D. The speed of a link is its capacity in Mbps, and the speed of a route is the speed of its slowest link. The links and capacities are: SA 8, SB 6, AC 4, AD 7, BC 9, BD 4, CT 6 and DT 5. The manager wants a route whose speed is as large as possible and uses dynamic programming, working backwards from T.
    (a)
    What is the speed of the route S, A, C, T?
    [1 mark]
    • A44 Mbps
    • B66 Mbps
    • C88 Mbps
    • D1818 Mbps
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Working backwards, what is the greatest speed that can be achieved from A to T?
    [1 mark]
    • A44 Mbps
    • B55 Mbps
    • C77 Mbps
    • D66 Mbps
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Given that the best speed from A to T is 55 Mbps, complete the dynamic programming to find the best route from S to T and its speed.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: best speed from B to T is max⁡(min⁡(9,6), min⁡(4,5))=6\max(\min(9,6),\,\min(4,5))=6 via C
    B1: from S,
    max⁡(min⁡(8,5), min⁡(6,6))=6\max(\min(8,5),\,\min(6,6))=6 via B; the best route is S, B, C, T with speed 66 Mbps
    Accept: a table showing stage, state, action and value

    Total for question 2: 4 marks

  3. 3
    A firm has 5 engineers to share between three projects, and all five must be used. The profit, in £ thousand, when a project is given 0, 1, 2, 3, 4 or 5 engineers is: Project 1: 0, 7, 9, 10, 11, 17. Project 2: 0, 6, 9, 13, 15, 16. Project 3: 0, 1, 7, 14, 18, 25. The firm uses dynamic programming to maximise the total profit. Stage 1 is Project 3, stage 2 is Projects 2 and 3 together, and stage 3 is all three projects. The state is the number of engineers available at that stage and the action is the number given to the project being considered.
    (a)
    Find the value of the best allocation of 4 engineers to Projects 2 and 3 together, and say how many go to Project 2, showing the options you compare.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: for each action k=0,1,…,4k=0,1,\dots,4 engineers to Project 2, profit of Project 2 plus the best profit for Project 3 with the remaining 4−k4-k (stage 1 values 18,14,7,1,018, 14, 7, 1, 0)
    A1: the five totals
    18,20,16,14,1518, 20, 16, 14, 15
    A1: best is
    2020, with 1 engineer to Project 2 (and 3 to Project 3)
    Accept: a table with columns stage, state, action, value
    (b)
    The stage 2 values for 0,1,2,3,40, 1, 2, 3, 4 and 55 engineers are 0,6,9,14,200, 6, 9, 14, 20 and 2525. Complete the dynamic programming to find how the 5 engineers should be allocated and the maximum profit.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: for kk engineers to Project 1, profit of Project 1 plus the stage 2 value for 5−k5-k
    A1: totals
    25,27,23,19,17,1725, 27, 23, 19, 17, 17 for k=0,1,…,5k=0,1,\dots,5
    A1: maximum profit £
    2727 thousand, with 1 engineer to Project 1
    A1: back-tracking: 1 engineer to Project 2 (from the best action for 4 engineers) and 3 to Project 3

    Accept: a table with columns stage, state, action and value

    Total for question 3: 7 marks

  4. 4
    A delivery firm has a network of roads from its depot S to a customer T, with junctions A to H. The roads and their lengths, in km, are: SA 7, SB 10, SC 9, AD 7, AF 11, BD 8, BE 7, BF 10, CE 12, CF 11, DG 9, DH 10, EG 8, EH 10, FH 2, GT 8 and HT 9. Dynamic programming is used, working backwards from T. Stage 1 is the final step into T (from G or H), stage 2 is the step from D, E or F, stage 3 is the step from A, B or C, and stage 4 is the step from S. The state is the vertex and the action is the next vertex.
    (a)
    Complete the dynamic programming in a table with columns stage, state, action and value to find the shortest route from S to T and its length.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: working backwards from T: stage 1 values G 88 and H 99
    A1: stage 2: D
    1717 (via G), E 1616 (via G), F 1111 (via H)
    M1: stage 3: each state takes the minimum of (arc
    ++ value of the next vertex)
    A1: A
    2222 (via F), B 2121 (via F), C 2222 (via F)
    M1: stage 4: S compares
    7+227+22, 10+2110+21, 9+229+22
    A1: S
    2929 via A; shortest route S, A, F, H, T of length 2929 km
    (b)
    A delivery vehicle cannot travel more than 99 km along any single road. Use dynamic programming to find a route in which the longest single road is as short as possible, and decide whether the route in (a) can be used.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: at each state, value is the minimum over next vertices of the larger of (road length, value of the next vertex)
    A1: stage 1: G
    88, H 99; stage 2: D 99, E 88, F 99
    A1: stage 3: A
    99 (via D), B 88 (via E), C 1111 (via F)
    A1: stage 4: S
    99 via A, route S, A, D, G, T with longest road 99 km
    B1: length of this route
    7+7+9+8=317+7+9+8=31 km
    R1: the route in (a) contains the
    1111 km road AF, over the limit, so it cannot be used; S, A, D, G, T can be used, and is 22 km longer

    Total for question 4: 12 marks

End of questions

Subtopic tests