Dynamic programmingEdexcel A-Level Further Maths: Subtopic test

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]

   • A$13$ km
   • B$11$ km
   • C$9$ km
   • D$7$ km

   (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

   (c)

   Given that the shortest distance from A to T is $9$ km, complete the dynamic programming to find the shortest route from S to T and its length.

   [2 marks]

   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]

   • A$4$ Mbps
   • B$6$ Mbps
   • C$8$ Mbps
   • D$18$ Mbps

   (b)

   Working backwards, what is the greatest speed that can be achieved from A to T?

   [1 mark]

   • A$4$ Mbps
   • B$5$ Mbps
   • C$7$ Mbps
   • D$6$ Mbps

   (c)

   Given that the best speed from A to T is $5$ Mbps, complete the dynamic programming to find the best route from S to T and its speed.

   [2 marks]

   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]

   (b)

   The stage 2 values for $0, 1, 2, 3, 4$ and $5$ engineers are $0, 6, 9, 14, 20$ and $25$. Complete the dynamic programming to find how the 5 engineers should be allocated and the maximum profit.

   [4 marks]

   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]

   (b)

   A delivery vehicle cannot travel more than $9$ 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]

   Total for question 4: 12 marks

End of questions