User interface language: English | Español

Date November 2019 Marks available 6 Reference code 19N.3.AHL.TZ0.Hdm_1
Level Additional Higher Level Paper Paper 3 Time zone Time zone 0
Command term Find and Use Question number Hdm_1 Adapted from N/A

Question

A driver needs to make deliveries to five shops AA, BB, CC, DD and EE. The driver starts and finishes his journey at the warehouse WW. The driver wants to find the shortest route to visit all the shops and return to the warehouse. The distances, in kilometres, between the locations are given in the following table.

By deleting WW, use the deleted vertex algorithm to find a lower bound for the length of a route that visits every shop, starting and finishing at WW.

[6]
a.

Starting from WW, use the nearest-neighbour algorithm to find a route which gives an upper bound for this problem and calculate its length.

[4]
b.

Markscheme

deleting WW and its adjacent edges, the minimal spanning tree is

   A1A1A1A1

Note: Award the A1’s for either the edges or their weights.

the minimum spanning tree has weight = 54

Note: Accept a correct drawing of the minimal spanning tree.

adding in the weights of 2 deleted edges of least weight WBWB and WCWC       (M1)
lower bound = 54 + 36 + 39

= 129         A1

[6 marks]

a.

attempt at the nearest-neighbour algorithm      M1

WBWB
BABA
ADAD
DEDE
ECEC
CWCW         A1

Note: Award M1 for a route that begins with WBWB and then BABA.

upper bound = 36 + 11 + 15 + 12 + 22 + 39 = 135       (M1)A1

[4 marks]

b.

Examiners report

[N/A]
a.
[N/A]
b.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman
Show 87 related questions
Topic 3—Geometry and trigonometry

View options