Problem

The table shows the shortest distances, in miles, between ten towns, A, B, C, D, E, F, G, H, J and K.

	A	B	C	D	E	F	G	H	J	K
A	–	16	26	19	22	34	30	41	45	36
B	16	–	10	15	38	33	40	25	29	20
C	26	10	–	12	39	30	31	15	19	10
D	19	15	12	–	33	18	25	28	31	22
E	22	38	39	33	–	15	8	33	20	29
F	34	33	30	18	15	–	7	24	19	28
G	30	40	31	25	8	7	–	25	12	21
H	41	25	15	28	33	24	25	–	13	5
J	45	29	19	31	20	19	12	13	–	9
K	36	20	10	22	29	28	21	5	9	–

(a) Explain the difference between the classical Travelling Salesman Problem and the practical Travelling Salesman Problem.

Kenzo must visit each town at least once, starting and finishing at A. Kenzo wishes to minimise the total distance travelled.

(b) Use Prim’s algorithm, starting at A, to obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.

(c) Use your answer to part (b) to determine an initial upper bound for the length of Kenzo’s route.

(d) Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Kenzo’s route. Write down the route that gives this upper bound.

Using the answer to part (d), and given that the length of the nearest neighbour route starting at G is 145 miles,

(e) state which of these two nearest neighbour routes gives the better upper bound. Give a reason for your answer.

(f) By deleting A and all of its arcs, obtain a lower bound for the length of Kenzo’s route.

(g) State the smallest interval that must contain the optimal length of Kenzo’s route.