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 A , B , C , D and E . The driver starts and finishes his journey at the warehouse W . 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 W , use the deleted vertex algorithm to find a lower bound for the length of a route that visits every shop, starting and finishing at W .

[6]
a.

Starting from W , 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 W 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 WB and WC       (M1)
lower bound = 54 + 36 + 39

= 129         A1

[6 marks]

a.

attempt at the nearest-neighbour algorithm      M1

WB
BA
AD
DE
EC
CW          A1

Note: Award M1 for a route that begins with WB and then BA .

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