| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.8 This is a standard D1 nearest neighbour algorithm question requiring straightforward application of taught procedures: reading from a table, applying the algorithm mechanically, and understanding upper/lower bounds. All parts follow textbook templates with no novel problem-solving required, making it easier than average A-level maths questions. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \cline { 2 - 7 } \multicolumn{1}{c|}{} | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | \(\boldsymbol { F }\) |
| \(\boldsymbol { A }\) | - | 15 | 11 | 14 | 27 | 12 |
| \(\boldsymbol { B }\) | 15 | - | 13 | 19 | 24 | 15 |
| \(\boldsymbol { C }\) | 11 | 13 | - | 10 | 19 | 12 |
| \(\boldsymbol { D }\) | 14 | 19 | 10 | - | 26 | 15 |
| \(\boldsymbol { E }\) | 27 | 24 | 19 | 26 | - | 27 |
| \(\boldsymbol { F }\) | 12 | 15 | 12 | 15 | 27 | - |
| Answer | Marks | Guidance |
|---|---|---|
| \(AB + BC + CD + DE + EF + FA = 15 + 13 + 10 + 26 + 27 + 12 = 103\) minutes | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| It is a solution/route/Hamiltonian cycle that exists, so the optimal solution cannot be worse (longer) than this | B1B1 | B1 for "it is a valid tour/route", B1 for "therefore minimum cannot exceed this value" |
| Answer | Marks | Guidance |
|---|---|---|
| From \(A\): nearest is \(C\) (11) | M1 | For attempt at nearest neighbour from \(A\) |
| From \(C\): nearest unvisited is \(D\) (10) | ||
| From \(D\): nearest unvisited is \(F\) (15) | ||
| From \(F\): nearest unvisited is \(B\) (15) | A1 | For correct route |
| From \(B\): nearest unvisited is \(E\) (24) | ||
| Return to \(A\): \(EA = 27\) | ||
| Route: \(ACDFBEA\) | A1 | cao |
| Total: \(11 + 10 + 15 + 15 + 24 + 27 = 102\) minutes | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Delete \(A\) and find minimum spanning tree of \(B, C, D, E, F\) | M1 | |
| Minimum spanning tree: \(CD = 10\), \(BC = 13\), \(CF\) or \(DF = 12\) or \(15\), \(BE\) or \(CE\) or \(DE\) = 24 or 19 or 26 | M1 | For attempt at MST |
| \(CD(10) + BC(13) + CF(12) + CE(19) = 54\) | A1 | For correct MST with value 54 |
| Add two shortest edges from \(A\): \(AC = 11\) and \(AD = 14\) | M1 | |
| Lower bound \(= 54 + 11 + 14 = 79\) minutes | A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| 75 is less than the lower bound of 79, so it is impossible to complete the tour in 75 minutes | B1 | Must reference lower bound of 79 (or their lower bound from (d)) |
## Question 4:
**(a)**
| $AB + BC + CD + DE + EF + FA = 15 + 13 + 10 + 26 + 27 + 12 = 103$ minutes | B1 | cao |
**(b)**
| It is a solution/route/Hamiltonian cycle that exists, so the optimal solution cannot be worse (longer) than this | B1B1 | B1 for "it is a valid tour/route", B1 for "therefore minimum cannot exceed this value" |
**(c)**
| From $A$: nearest is $C$ (11) | M1 | For attempt at nearest neighbour from $A$ |
| From $C$: nearest unvisited is $D$ (10) | | |
| From $D$: nearest unvisited is $F$ (15) | | |
| From $F$: nearest unvisited is $B$ (15) | A1 | For correct route |
| From $B$: nearest unvisited is $E$ (24) | | |
| Return to $A$: $EA = 27$ | | |
| Route: $ACDFBEA$ | A1 | cao |
| Total: $11 + 10 + 15 + 15 + 24 + 27 = 102$ minutes | A1 | cao |
**(d)**
| Delete $A$ and find minimum spanning tree of $B, C, D, E, F$ | M1 | |
| Minimum spanning tree: $CD = 10$, $BC = 13$, $CF$ or $DF = 12$ or $15$, $BE$ or $CE$ or $DE$ = 24 or 19 or 26 | M1 | For attempt at MST |
| $CD(10) + BC(13) + CF(12) + CE(19) = 54$ | A1 | For correct MST with value 54 |
| Add two shortest edges from $A$: $AC = 11$ and $AD = 14$ | M1 | |
| Lower bound $= 54 + 11 + 14 = 79$ minutes | A1 | cao |
**(e)**
| 75 is less than the lower bound of 79, so it is impossible to complete the tour in 75 minutes | B1 | Must reference lower bound of 79 (or their lower bound from (d)) |4 Sarah is a mobile hairdresser based at $A$. Her day's appointments are at five places: $B , C , D , E$ and $F$. She can arrange the appointments in any order. She intends to travel from one place to the next until she has visited all of the places, starting and finishing at $A$. The following table shows the times, in minutes, that it takes to travel between the six places.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\cline { 2 - 7 }
\multicolumn{1}{c|}{} & $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { E }$ & $\boldsymbol { F }$ \\
\hline
$\boldsymbol { A }$ & - & 15 & 11 & 14 & 27 & 12 \\
\hline
$\boldsymbol { B }$ & 15 & - & 13 & 19 & 24 & 15 \\
\hline
$\boldsymbol { C }$ & 11 & 13 & - & 10 & 19 & 12 \\
\hline
$\boldsymbol { D }$ & 14 & 19 & 10 & - & 26 & 15 \\
\hline
$\boldsymbol { E }$ & 27 & 24 & 19 & 26 & - & 27 \\
\hline
$\boldsymbol { F }$ & 12 & 15 & 12 & 15 & 27 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Sarah decides to visit the places in the order $A B C D E F A$. Find the travelling time of this tour.
\item Explain why this answer can be considered as being an upper bound for the minimum travelling time of Sarah's tour.
\item Use the nearest neighbour algorithm, starting from $A$, to find another upper bound for the minimum travelling time of Sarah's tour.
\item By deleting $A$, find a lower bound for the minimum travelling time of Sarah's tour.
\item Sarah thinks that she can reduce her travelling time to 75 minutes. Explain why she is wrong.
\end{enumerate}
\hfill \mbox{\textit{AQA D1 2013 Q4 [12]}}