Edexcel A-Level Further Maths
Dynamic programming
Total 27 marks
Name
Class
Date
- 1A 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 km
- B km
- C km
- D 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 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 via D
B1: from S, via B; the shortest route is S, B, D, T of length km
Accept: a table showing stage, state, action and valueTotal for question 1: 4 marks
- 2Messages 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 Mbps
- B Mbps
- C Mbps
- D 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]- A Mbps
- B Mbps
- C Mbps
- D Mbps
Show the mark scheme
Mark scheme
Answer: B(c)Given that the best speed from A to T is 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 via C
B1: from S, via B; the best route is S, B, C, T with speed Mbps
Accept: a table showing stage, state, action and valueTotal for question 2: 4 marks
- 3A 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 engineers to Project 2, profit of Project 2 plus the best profit for Project 3 with the remaining (stage 1 values )
A1: the five totals
A1: best is , 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 and engineers are and . 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 engineers to Project 1, profit of Project 1 plus the stage 2 value for
A1: totals for
A1: maximum profit £ 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 valueTotal for question 3: 7 marks
- 4A 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 and H
A1: stage 2: D (via G), E (via G), F (via H)
M1: stage 3: each state takes the minimum of (arc value of the next vertex)
A1: A (via F), B (via F), C (via F)
M1: stage 4: S compares , ,
A1: S via A; shortest route S, A, F, H, T of length km(b)A delivery vehicle cannot travel more than 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 , H ; stage 2: D , E , F
A1: stage 3: A (via D), B (via E), C (via F)
A1: stage 4: S via A, route S, A, D, G, T with longest road km
B1: length of this route km
R1: the route in (a) contains the km road AF, over the limit, so it cannot be used; S, A, D, G, T can be used, and is km longerTotal for question 4: 12 marks
End of questions