| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Asymmetric Distance Matrix |
| Difficulty | Easy -1.3 This is a straightforward application of basic TSP concepts requiring only table reading and arithmetic. Parts (a-b) involve simple addition of given values, part (c) applies a standard algorithm mechanically, and part (d) requires comparing three numbers. No optimization insight or problem-solving is needed beyond following prescribed procedures. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| \backslashbox{From}{To} | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) |
| A | - | 8 | 6 | 11 |
| B | 14 | - | 13 | 25 |
| C | 14 | 9 | - | 17 |
| \(\boldsymbol { D }\) | 26 | 10 | 18 | - |
| Answer | Marks | Guidance |
|---|---|---|
| \(A\) \(B\) \(C\) \(D\) \(A\) with values \(8\) \(13\) \(17\) \(26\) = \(64\) | M1, A1 | 4 numbers (either part) (2 marks total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(A\) \(D\) \(C\) \(B\) \(A\) with values \(11\) \(18\) \(9\) \(14\) = \(52\) | A1 | (1 mark total) |
| Answer | Marks | Guidance |
|---|---|---|
| \(A\) \(C\) \(B\) \(D\) \(A\) with values \(6\) \(9\) \(25\) \(26\) = \(66\frac{1}{2}\) | M1, M1, A1, B1 | Tour; Visits every vertex; Correct order (4 marks total) |
| Alternative if matrix used: M1 3 numbers (all different rows and columns); M1 4th number; A1 correct numbers; B1 66 |
| Answer | Marks | Guidance |
|---|---|---|
| \(52\) | B1F | Allow "part (b)" (1 mark total) |
**3(a)**
| $A$ $B$ $C$ $D$ $A$ with values $8$ $13$ $17$ $26$ = $64$ | M1, A1 | 4 numbers (either part) (2 marks total) |
**3(b)**
| $A$ $D$ $C$ $B$ $A$ with values $11$ $18$ $9$ $14$ = $52$ | A1 | (1 mark total) |
**3(c)**
| $A$ $C$ $B$ $D$ $A$ with values $6$ $9$ $25$ $26$ = $66\frac{1}{2}$ | M1, M1, A1, B1 | Tour; Visits every vertex; Correct order (4 marks total) |
| Alternative if matrix used: M1 3 numbers (all different rows and columns); M1 4th number; A1 correct numbers; B1 66 | | |
**3(d)**
| $52$ | B1F | Allow "part (b)" (1 mark total) |3 Mark is driving around the one-way system in Leicester. The following table shows the times, in minutes, for Mark to drive between four places: $A , B , C$ and $D$. Mark decides to start from $A$, drive to the other three places and then return to $A$.
Mark wants to keep his driving time to a minimum.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\backslashbox{From}{To} & $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ \\
\hline
A & - & 8 & 6 & 11 \\
\hline
B & 14 & - & 13 & 25 \\
\hline
C & 14 & 9 & - & 17 \\
\hline
$\boldsymbol { D }$ & 26 & 10 & 18 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Find the length of the tour $A B C D A$.
\item Find the length of the tour $A D C B A$.
\item Find the length of the tour using the nearest neighbour algorithm starting from $A$.
\item Write down which of your answers to parts (a), (b) and (c) gives the best upper bound for Mark's driving time.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q3 [8]}}