5 Phil, a squash coach, wishes to buy some equipment for his club. In a town centre, there are six shops, \(G , I , N , R , S\) and \(T\), that sell the equipment.
The time, in seconds, to walk between each pair of shops is shown in the table.
Phil intends to check prices by visiting each of the six shops before returning to his starting point.
| \(\boldsymbol { G }\) | \(\boldsymbol { I }\) | \(N\) | \(\boldsymbol { R }\) | \(\boldsymbol { S }\) | \(T\) |
| \(\boldsymbol { G }\) | - | 81 | 82 | 86 | 72 | 76 |
| \(\boldsymbol { I }\) | 81 | - | 80 | 82 | 68 | 73 |
| \(\boldsymbol { N }\) | 82 | 80 | - | 84 | 70 | 74 |
| \(\boldsymbol { R }\) | 86 | 82 | 84 | - | 74 | 70 |
| \(\boldsymbol { S }\) | 72 | 68 | 70 | 74 | - | 64 |
| \(T\) | 76 | 73 | 74 | 70 | 64 | - |
- Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time.
- Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a).
- By deleting \(S\), find a lower bound for Phil's minimum walking time.
\includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-11_2484_1709_223_153}