Write down a way in which the nearest neighbour method can fail to solve the problem of finding a least weight cycle through all the vertices of a network.
Explain why, when trying to find a least weight cycle through all the vertices of a network, an ad hoc method may be preferable to an algorithmic approach.
The distance matrix below represents a network connecting six viewpoints \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F . The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists.
The distances are measured in km.
A blank shows that there is no direct route between the two viewpoints.
A
B
C
D
E
F
A
6
4
B
6
5
2
9
C
5
15
7
6
D
4
2
15
5
E
9
7
5
F
6
Draw the network on the vertices given in the Printed Answer Booklet.
Apply the nearest neighbour method, starting from A.
A hiker wants to travel between the six viewpoints, starting and finishing at A.
The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.
Show that the hiker does not need to travel as far as 50 km .
Use an appropriate algorithm to find the shortest distance from F to each of the other viewpoints.
Complete the table in the Printed Answer Book to show the shortest distance between each pair of viewpoints.
Use your answer to part (g) to find a lower bound for the distance the hiker must travel by initially deleting vertex A.