| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.8 This is a standard algorithmic application question from D2. Part (a) requires mechanical application of nearest neighbour algorithm (selecting minimum values from table), part (b) uses the standard minimum spanning tree deletion method for lower bounds, and part (c) simply requires writing the inequality from parts (a) and (b). All procedures are routine textbook exercises with no problem-solving insight required, though the table lookup and arithmetic takes some care. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | |
| \(A\) | - | 98 | 123 | 68 | 96 | 71 |
| \(B\) | 98 | - | 74 | 129 | 47 | 120 |
| \(C\) | 123 | 74 | - | 102 | 111 | 63 |
| \(D\) | 68 | 129 | 102 | - | 85 | 59 |
| \(E\) | 96 | 47 | 111 | 85 | - | 115 |
| \(F\) | 71 | 120 | 63 | 59 | 115 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(A_{68}\ D_{59}\ F_{63}\ C_{74}\ B_{47}\ E_{96}\ A\), total \(= 407\) km | M1 A1 A1(3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(E_{47}\ B_{74}\ C_{63}\ F_{59}\ D\) with connections via \(A\) (68, 71) | M1 | |
| \(243 + 68 + 71 = 382\) km | A1 A1(3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(382 <\) optimal route \(\leq 407\) | M1 A1(2) |
## Question 4:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $A_{68}\ D_{59}\ F_{63}\ C_{74}\ B_{47}\ E_{96}\ A$, total $= 407$ km | M1 A1 A1(3) | |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $E_{47}\ B_{74}\ C_{63}\ F_{59}\ D$ with connections via $A$ (68, 71) | M1 | |
| $243 + 68 + 71 = 382$ km | A1 A1(3) | |
### Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $382 <$ optimal route $\leq 407$ | M1 A1(2) | |
---4. The table shows the least distances, in km, between six towns $A , B , C , D , E$ and $F$.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
& $A$ & $B$ & $C$ & $D$ & $E$ & $F$ \\
\hline
$A$ & - & 98 & 123 & 68 & 96 & 71 \\
\hline
$B$ & 98 & - & 74 & 129 & 47 & 120 \\
\hline
$C$ & 123 & 74 & - & 102 & 111 & 63 \\
\hline
$D$ & 68 & 129 & 102 & - & 85 & 59 \\
\hline
$E$ & 96 & 47 & 111 & 85 & - & 115 \\
\hline
$F$ & 71 & 120 & 63 & 59 & 115 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Starting at $A$, and making your method clear, find an upper bound for the travelling salesman problem using the nearest neighbour algorithm.
\item By deleting $A$, and all of its arcs, find a lower bound for the travelling salesman problem.
\item Write down an inequality about the length of the optimal route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q4 [8]}}