AQA D1 2010 June — Question 5 10 marks

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2010
SessionJune
Marks10
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicTravelling Salesman
TypeNearest Neighbour Algorithm
DifficultyModerate -0.8 This is a standard textbook application of nearest neighbour algorithm and minimum spanning tree deletion method for the travelling salesman problem. The question requires only mechanical application of well-defined algorithms with no problem-solving insight or novel reasoning—students simply follow the procedures they've been taught. While it has multiple parts and requires careful arithmetic, these are routine D1 techniques that are easier than average A-level maths questions overall.
Spec7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree
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. $$\begin{array}{c|cccccc} & G & I & N & R & S & T \\ \hline G & - & 81 & 82 & 86 & 72 & 76 \\ I & 81 & - & 80 & 82 & 68 & 73 \\ N & 82 & 80 & - & 84 & 70 & 74 \\ R & 86 & 82 & 84 & - & 74 & 70 \\ S & 72 & 68 & 70 & 74 & - & 64 \\ T & 76 & 73 & 74 & 70 & 64 & - \\ \end{array}$$
  1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time. [4 marks]
  2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a). [1 mark]
  3. By deleting \(S\), find a lower bound for Phil's minimum walking time. [5 marks]
Question 5:
5
Question 5:
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.

$$\begin{array}{c|cccccc}
 & G & I & N & R & S & T \\
\hline
G & - & 81 & 82 & 86 & 72 & 76 \\
I & 81 & - & 80 & 82 & 68 & 73 \\
N & 82 & 80 & - & 84 & 70 & 74 \\
R & 86 & 82 & 84 & - & 74 & 70 \\
S & 72 & 68 & 70 & 74 & - & 64 \\
T & 76 & 73 & 74 & 70 & 64 & - \\
\end{array}$$

\begin{enumerate}[label=(\alph*)]
\item Use the nearest neighbour algorithm starting from $S$ to find an upper bound for Phil's minimum walking time. [4 marks]

\item Write down a tour starting from $N$ which has a total walking time equal to your answer to part (a). [1 mark]

\item By deleting $S$, find a lower bound for Phil's minimum walking time. [5 marks]
\end{enumerate}

\hfill \mbox{\textit{AQA D1 2010 Q5 [10]}}
This paper (8 questions)
View full paper
Q1 4 Q2 9 Q3 11 Q4 14 Q5 10 Q6 17 Q7 6 Q8 4