D2 June 2013 (R) Q2

EdexcelOld spec8 marksTravelling Salesman

2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.

	A	B	C	D	E	F
A	–	122	217	137	109	82
B	122	–	110	130	128	204
C	217	110	–	204	238	135
D	137	130	204	–	98	211
E	109	128	238	98	–	113
F	82	204	135	211	113	–

Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.

(a) Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz’s route. You must state the shortcut(s) you use and the length of your upper bound. (2)

(b) Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Liz’s route. (2)

(d) Use your results to write down the smallest interval which you are confident contains the optimal length of the route. (1)

Mark scheme (a)

Scheme	Marks
E.g. If use CD as shortcut get 807 or if use CF + AD get 793	M1 A1
	(2)

Notes

a1M1: Their plausible shortcut leading to a value < 810 and a length below 810 stated.

a1A1: CAO – shortcut and length must be consistent.

(Examples shortcuts: CD = 807, CF + AD = 793, CF + BD = 664, AD + EF + FC = 715, DF + FC = 785 etc.)

Scheme	Marks
A F E D B C A	B1
82 113 98 130 110 217 = 750	B1
	(2)

Scheme	Marks
length of RMST = 439	B1
439 + 82 + 113 = 634	M1 A1
	(3)

Scheme	Marks
634 < optimal \(\leqslant\) 750	B1ft
	(1)
	8 marks