Edexcel International A Level Maths
The travelling salesman problem
Total 27 marks
Name
Class
Date
- 1A sales representative must visit four towns , , and , starting and finishing at . Every pair of towns is joined by a direct road. The distances in km are , , , , and . Each town is to be visited exactly once.(a)How many different tours are there, starting and finishing at , if a tour and its reverse are counted as the same?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)Which statement describes the classical travelling salesman problem, as opposed to the practical problem?[1 mark]- AEach vertex is visited exactly once
- BA vertex may be visited more than once
- CNot every vertex needs visiting
- DThe route need not return to the start
Show the mark scheme
Mark scheme
Answer: A(c)Find the length of the shortest tour for the classical problem.[2 marks]Show the mark scheme
Mark scheme
M1: all three tours considered, , ,
A1: shortest tour (or ) of length kmTotal for question 1: 4 marks
- 2A driver starts at a depot , delivers to three shops , and , and returns to . The only roads are , and , with lengths in km. The driver may pass through a junction more than once.(a)Why can the classical travelling salesman problem not be solved on this network?[1 mark]
- AThe network is not connected
- BEach shop is joined only to , so must be revisited
- CThe distances do not satisfy the triangle inequality
- D is not joined to every shop
Show the mark scheme
Mark scheme
Answer: B(b)What is the length of the shortest route that starts at , visits every shop and returns to ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(c)A fourth shop is added, joined only to by a road of length km. Find the length of the shortest route that visits all four shops and returns to .[2 marks]Show the mark scheme
Mark scheme
M1: every road travelled twice,
A1: km
Accept: route --------Total for question 2: 4 marks
- 3Four offices , , and are joined by a complete network of direct links. The lengths in km are , , , , and .(a)Show that the triangle inequality is not satisfied by this network.[3 marks]
Show the mark scheme
Mark scheme
M1: considers a triangle with its longest side, for example against
A1:
B1: the triangle inequality requires the longest side to be no more than the sum of the other two, so it fails
Accept: any correct statement that(b)Find the shortest tour that visits each office exactly once, starting and finishing at , and give its length.[4 marks]Show the mark scheme
Mark scheme
M1: all three tours considered, in either direction
A1:
A1: and
B1: shortest tour ---- of length kmTotal for question 3: 7 marks
- 4A bus must visit five stops , , , and , starting and finishing at . The only roads, with lengths in km, are , , , and . Stop is joined to the rest of the network only by .(a)(i) Explain why the classical travelling salesman problem has no solution on this network.[6 marks]
(ii) Find the shortest route that visits every stop and returns to , in which a stop may be revisited, and give its length.Show the mark scheme
Mark scheme
R1: (i) is joined only to
R1: so a route entering must leave by the same road, and cannot be visited only once
B1: (ii) the road must be travelled twice,
M1: the other four stops need the whole cycle ,
A1: route ------
A1: length km
Accept: the route in reverse, or starting at another vertex(b)A new road of length km is built. Show that there is now a tour visiting each stop exactly once, and find the values of for which this tour is shorter than the route found in (a).[6 marks]Show the mark scheme
Mark scheme
M1: tour using and so that each stop is visited once, -----
A1: the tour does not use
A1: length
M1: compares with
A1:
R1: when the new tour is shorter, and when the route in (a) is still the shortestTotal for question 4: 12 marks
End of questions