Edexcel A-Level Further Maths
The Travelling Salesman problem
Total 27 marks
Name
Class
Date
- 1A salesman must visit each of towns A, B, C, D and E once, starting and finishing at A. The distances in km between the towns are: AB 12, AC 10, AD 14, AE 8, BC 3, BD 7, BE 9, CD 6, CE 11 and DE 12.(a)Using the nearest neighbour algorithm starting at A, which town is visited immediately after E?[1 mark]
- AC
- BD
- CE
- DB
Show the mark scheme
Mark scheme
Answer: D(b)What is the weight of the minimum spanning tree for the five towns?[1 mark]- A26
- B40
- C24
- D33
Show the mark scheme
Mark scheme
Answer: A(c)Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the shortest route.[2 marks]Show the mark scheme
Mark scheme
M1: route A–E–B–C–D–A (nearest unvisited town each time, then back to A)
A1: upper bound 40 km
Accept: 8 + 9 + 3 + 6 + 14Total for question 1: 4 marks
- 2A courier must visit depots A, B, C, D and E and return to the start. The only direct roads and their lengths in km are: AB 6, BC 4, CD 5, DE 3, AE 12, BD 11 and CE 10.(a)What is the least distance between depots A and D?[1 mark]
- A17
- B18
- C15
- D12
Show the mark scheme
Mark scheme
Answer: C(b)Which statement describes the practical Travelling Salesman problem?[1 mark]- AEvery vertex is visited exactly once and the network must be complete
- BEvery vertex is visited at least once, and a vertex or arc may be used more than once
- CThe route may leave out some vertices
- DThe route does not have to return to its start
Show the mark scheme
Mark scheme
Answer: B(c)Find the least distance between B and D, and the least distance between C and E.[2 marks]Show the mark scheme
Mark scheme
B1: B to D = 9 (B–C–D, not the road BD of 11)
B1: C to E = 8 (C–D–E, not the road CE of 10)Total for question 2: 4 marks
- 3A delivery driver must visit five shops A, B, C, D and E, starting and finishing at A, and visiting each shop exactly once. The distances in km between the shops are: AB 15, AC 22, AD 25, AE 18, BC 10, BD 20, BE 12, CD 14, CE 16 and DE 9. These distances satisfy the triangle inequality.(a)Find a lower bound for the length of the shortest route by deleting shop A.[3 marks]
Show the mark scheme
Mark scheme
M1: minimum spanning tree of B, C, D and E, using BC 10, BE 12 and DE 9, weight 31
M1: adds the two shortest arcs from A, AB 15 and AE 18
A1: lower bound 64 km
Accept: 31 + 15 + 18(b)Use the nearest neighbour algorithm starting at A to find an upper bound, and hence write down an interval in which the length of the shortest route must lie.[4 marks]Show the mark scheme
Mark scheme
M1: A–B–C–D–E–A (nearest unvisited shop each time)
A1: upper bound 15 + 10 + 14 + 9 + 18 = 66 km
M1: uses lower bound from (a)
A1: 64 ≤ shortest route ≤ 66
Accept: follow-through from (a)Total for question 3: 7 marks
- 4An engineer must inspect six sites A, B, C, D, E and F, visiting each site once and returning to the start. The distances in km between the sites are: AB 11, AC 14, AD 20, AE 17, AF 9, BC 8, BD 15, BE 13, BF 12, CD 10, CE 16, CF 18, DE 7, DF 19 and EF 12. These distances satisfy the triangle inequality.(a)(i) Use Kruskal's algorithm to find a minimum spanning tree for the six sites, and state its weight.[6 marks]
(ii) Hence find an upper bound by doubling the weight of the tree.
(iii) Show that a shortcut gives an improved upper bound, and state the route and its length.Show the mark scheme
Mark scheme
M1: (i) arcs selected in order of size: DE 7, BC 8, AF 9, CD 10, AB 11 (BF 12 and EF 12 would form cycles)
A1: (i) weight 45
B1: (ii) upper bound 90 km
M1: (iii) shortcut: from E go directly to F instead of retracing the tree
A1: (iii) route F–A–B–C–D–E–F, length 9 + 11 + 8 + 10 + 7 + 12 = 57 km
R1: (iii) the shortcut is valid because EF = 12 is less than E–D–C–B–A–F = 45 (triangle inequality)(b)By deleting site A, find a lower bound for the length of the shortest route. Use it, with your answer to (a), to decide whether the route of length 57 km is the shortest possible. Justify your answer.[6 marks]Show the mark scheme
Mark scheme
M1: minimum spanning tree of B, C, D, E and F (DE 7, BC 8, CD 10, and BF or EF 12)
A1: weight 37
M1: adds the two shortest arcs from A, AF 9 and AB 11
A1: lower bound 57 km
R1: the lower bound equals the upper bound of 57 km
B1: so the shortest route is exactly 57 km, and F–A–B–C–D–E–F is optimal
Accept: follow-through from their upper bound in (a)(iii) for the conclusionTotal for question 4: 12 marks
End of questions