Classical and practical problems, table of least distances, nearest neighbour, minimum spanning tree with shortcuts.
12 original questions, 76 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.
A van driver must deliver to six shops in Cardiff, starting and finishing at the depot, and wants to keep the total distance as small as possible.
Explain the difference between the classical and the practical travelling salesman problems.
Explain why the length of any tour that visits every shop and returns to the depot is an upper bound for the length of the optimal route.
3 marks
Show answer
a) Classical: each vertex must be visited exactly once before returning to the start. Practical: each vertex must be visited at least once before returning to the start.b) The optimal route is the shortest of all possible tours, so any particular tour is at least as long as it: its length is an upper bound.
2
The table shows the least distances, in miles, between five villages in Cumbria, A, B, C, D and E. A district nurse starts and finishes at A and visits every village.
A
B
C
D
E
A
−
27
31
33
23
B
27
−
48
58
37
C
31
48
−
16
13
D
33
58
16
−
21
E
23
37
13
21
−
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of her route. Write your tour and its length in the table below.
3 marks
Show answer
A - E - C - D - B - A, 137 miles
3
The network below shows the direct roads between five farms, A to E. The number on each arc is the length of the road in km.
Complete the table of least distances below.
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour that visits every farm and returns to A.
4 marks
Show answer
a) AD = 28, AE = 28, BE = 20, CD = 19b) A - C - B - D - E - A, 65 km
4
The table shows the least travel times, in minutes, between six depots, A to F, used by a parcel company in Kent.
A
B
C
D
E
F
A
−
24
49
25
69
47
B
24
−
41
9
53
36
C
49
41
−
32
61
19
D
25
9
32
−
44
27
E
69
53
61
44
−
42
F
47
36
19
27
42
−
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour of the six depots.
Repeat the nearest neighbour algorithm, starting at D.
State the better upper bound, giving a reason for your answer.
5 marks
Show answer
a) A - B - D - F - C - E - A, 209 minutesb) D - B - A - F - C - E - D, 204 minutesc) 204 minutes, as it is the smaller
5
The network below shows the footpaths between six viewpoints, A to F, in a country park in Yorkshire. The numbers on the arcs are lengths in hundreds of metres. A ranger must visit every viewpoint, starting and finishing at A.
Apply the nearest neighbour algorithm, starting at A, directly to the network. Explain why it does not give a tour.
The table shows the least distances between the viewpoints.
A
B
C
D
E
F
A
−
8
12
23
26
29
B
8
−
10
15
24
21
C
12
10
−
23
14
25
D
23
15
23
−
9
6
E
26
24
14
9
−
11
F
29
21
25
6
11
−
Use the nearest neighbour algorithm on the table, starting at A, to find an upper bound for the length of the ranger's route.
Write down the route the ranger actually walks in the network, listing every viewpoint passed through.
7 marks
Show answer
a) A, B, C, E, D, F reached, but there is no arc from F back to A (every neighbour of F is visited), so the algorithm cannot complete a tour.b) A - B - C - E - D - F - A, 76 (7600 m)c) A - B - C - E - D - F - D - B - A
6
The table below shows the least distances, in km, between six sports centres, A to F, in a borough of London.
Use Prim's algorithm, starting at A, to find a minimum spanning tree for the table. You must state the order in which you select the arcs.
Hence find an initial upper bound for the length of a tour of the six centres.
Starting from the route that travels along every arc of the tree twice, use shortcuts to reduce the upper bound to below 160 km. State your tour and its length.
7 marks
Show answer
a) AB, BC, BE, AD, DF; weight 103 kmb) 206 kmc) e.g. A - D - F - C - B - E - A, 155 km
7
The table shows the least distances, in miles, between six towns, A to F, in Lincolnshire. The least distance between D and F is x miles, where x ≥ 20
A
B
C
D
E
F
A
−
63
49
31
38
46
B
63
−
56
53
25
72
C
49
56
−
48
40
67
D
31
53
48
−
28
x
E
38
25
40
28
−
47
F
46
72
67
x
47
−
The nearest neighbour algorithm, starting at A, is applied to the table. The tour begins A, D, F.
Find the range of possible values of x
Complete the tour and find, in terms of x, the upper bound it gives.
Given instead that x = 35, use the nearest neighbour algorithm, starting at A, to find an upper bound.
6 marks
Show answer
a) 20 ≤ x < 28b) A - D - F - E - B - C - A, 208 + xc) A - D - E - B - C - F - A, 253 miles
8
The table shows the least distances, in km, between six branches of a bank in Northern Ireland, A to F. An auditor visits every branch and returns to her starting point.
A
B
C
D
E
F
A
−
37
60
52
51
46
B
37
−
59
49
39
30
C
60
59
−
10
22
29
D
52
49
10
−
24
23
E
51
39
22
24
−
19
F
46
30
29
23
19
−
Use the nearest neighbour algorithm, starting at C, to find an upper bound for the length of her tour.
Kofi suggests the tour A - B - F - E - C - D - A.
Find the length of Kofi's tour.
State the best upper bound you now have, and explain whether you can say that it is the length of the optimal tour.
6 marks
Show answer
a) C - D - F - E - B - A - C, 188 kmb) 170 kmc) 170 km; it is an upper bound only, so the optimal tour could still be shorter (a lower bound of 170 would be needed to show it is optimal).
9
The network below shows the roads between seven villages, A to G, on Anglesey. The numbers on the arcs are distances in km. A mobile library must visit every village, starting and finishing at A.
Complete the table of least distances below.
Use the nearest neighbour algorithm on the completed table, starting at A, to find an upper bound for the length of the route.
Write down the route in the network that the library van actually drives for your tour in (b).
The nearest neighbour algorithm starting at G gives the tour G - E - D - B - A - C - F - G.
Find the length of this tour and state, with a reason, which upper bound is better.
9 marks
Show answer
a) AG = 48, BG = 37, CE = 27, DG = 28b) A - C - D - B - F - G - E - A, 123 kmc) A - C - D - B - D - F - G - E - D - Ad) 110 km; 110 km is better as it is smaller
10
The table shows the least travel times, in minutes, between five care homes, A to E, in Leicester. A visiting doctor plans a tour of all five homes, returning to the first.
A
B
C
D
E
A
−
29
11
22
33
B
29
−
27
35
57
C
11
27
−
14
30
D
22
35
14
−
43
E
33
57
30
43
−
Use the nearest neighbour algorithm, starting at each of the five homes in turn, to find five tours. State the length of each tour.
Hence state the best upper bound for the length of the optimal tour.
Explain why the doctor may start her tour at any of the homes.
7 marks
Show answer
a) A: A - C - D - B - E - A 150; B: B - C - A - D - E - B 160; C: C - A - D - B - E - C 155; D: D - C - A - B - E - D 154; E: E - C - A - D - B - E 155b) 150 minutesc) A tour is a cycle through every vertex, so the same cycle can be started at any vertex with the same length.
11
The table shows the least distances, in km, between six warehouses, A to F, near Birmingham. The least distance between B and D is x km, where 25 < x < 63
A
B
C
D
E
F
A
−
54
50
60
85
59
B
54
−
20
x
35
26
C
50
20
−
44
40
9
D
60
x
44
−
42
47
E
85
35
40
42
−
49
F
59
26
9
47
49
−
Given that x < 35, use the nearest neighbour algorithm, starting at A, to find an upper bound, in terms of x, for the length of a tour of the warehouses.
Given instead that x > 35, use the nearest neighbour algorithm, starting at A, to find an upper bound.
Find the set of values of x for which the nearest neighbour algorithm, starting at A, gives an upper bound of less than 240 km.
8 marks
Show answer
a) A - C - F - B - D - E - A, 212 + xb) A - C - F - B - E - D - A, 222 kmc) 25 < x < 28 or 35 < x < 63
12
A tour guide in Edinburgh plans a walking tour of seven sites, A to G, starting and finishing at the hotel at A. The table below shows the least walking times, in minutes, between the sites.
Use Prim's algorithm, starting at A, to find a minimum spanning tree. You must state the order in which you select the arcs, and its weight.
Hence find an initial upper bound for the length of the tour.
Use a shortcut to reduce this upper bound to below 140 minutes. State the tour you use.
Use the nearest neighbour algorithm, starting at A, to find a second upper bound.
State, with a reason, the best upper bound you have found.
11 marks
Show answer
a) AD, AF, FG, GB, BC, CE; weight 97 minutesb) 194 minutesc) e.g. A - F - G - B - C - E - D - A, 128 minutesd) A - D - F - G - B - C - E - A, 146 minutese) 128 minutes, the smallest upper bound
Your score
Answer the questions above and your score appears here.
Every question here is original and written by Robinson Tuition. It follows the Edexcel A-level Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.