D2 January 2006 Q6

EdexcelOld spec13 marksTravelling Salesman

6.

Network of roads between the towns with distances in km

The network in the figure above, shows the distances in km, along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A.

By deleting D, a lower bound for the length of the route was found to be 586 km.
By deleting F, a lower bound for the length of the route was found to be 590 km.

(a) By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer. (5)
(b) By inspection complete the table of least distances. (4)
ABCDEFGH
A-848513817314952
B84-13077126213222136
C85130-53888392
D1387753-49190
E1731268849-100180215
F21383100-163115
G14922292180163-97
H5213619021511597-

The table can now be taken to represent a complete network.

The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km.
Starting at F, an upper bound for the length of the route was found to be 707 km.

(c) Starting at C, use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the three, giving a reason for your answer. (4)
‹ Previous23 of 24 in Travelling SalesmanNext ›