D2 June 2007 Q1

EdexcelOld spec11 marksTravelling Salesman

The network above shows the distances, in miles, between seven gift shops, \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\).

The area manager needs to visit each shop. She will start and finish at shop A and wishes to minimise the total distance travelled.

(a) By inspection, complete the two copies of the table of least distances below. (4)

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	–		15	36		53	23
\(B\)		–	17	38	49	80	49
\(C\)	15	17	–	21		62	32
\(D\)	36	38	21	–	11	42
\(E\)		49		11	–	31	61
\(F\)	53	80	62	42	31	–	30
\(G\)	23	49	32		61	30	–

(b) Starting at A, and making your method clear, find an upper bound for the route length, using the nearest neighbour algorithm. (3)