D2 June 2014 (R) Q2

EdexcelOld spec10 marksTravelling Salesman

(a) Explain the difference between the classical and the practical travelling salesperson problem. (2)

	A	B	C	D	E	F
A	–	65	48	15	30	40
B	65	–	50	51	35	26
C	48	50	–	37	20	34
D	15	51	37	–	17	25
E	30	35	20	17	–	14
F	40	26	34	25	14	–

The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Keith needs to visit each town, starting and finishing at A, and wishes to minimise the total distance he will travel.

(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. You must state your route and its length. (3)

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

Mark scheme (a)

Scheme	Marks
In the practical problem each vertex must be visited at least once. In the classical problem each vertex must be visited just once.	B2, 1, 0
	(2)

Notes

a1B1: Understands the difference is connected to the number of times each vertex may be visited.

a2DB1: Correctly identifies which is classical and which is practical and correctly states the difference.

Mark scheme (b)

Scheme	Marks
A D E F B C A 15 + 17 + 14 + 26 + 50 + 48 = 170	M1 A1 A1
	(3)

Notes

b1M1: Nearest neighbour A – D – E – F – B – C – or accept 145623 across top of table (condone lack of return to start).

b1A1: Route correctly stated, must return to A, accept link back to A.

b2A1: Length correctly stated. Do not ISW if candidates then go on to double the route length.

Residual minimum spanning tree B–F 26, F–E 14, E–D 17, E–C 20 — Mark scheme (c)

Scheme	Marks

RMST weight = 26 + 14 + 17 + 20 = 77 (km)	M1 A1
Lower bound = 77 + 15 + 30 = 122 (km)	A1
	(3)

Mark scheme (d)

Scheme	Marks
122 \(\leqslant\) length \(\leqslant\) 170	B2,1,0
	(2)
	10 marks

Notes

d1B1ft: Their correct numbers correctly used (their upper bound must be a cycle and their lower bound must have scored M1 in (c)), accept any inequalities or any indication of interval from their 122 to their 170.

d2B2: CAO including correct inequalities (but condone 122 < length \(\leqslant\) 170).