| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.3 This is a standard application of two algorithmic procedures (nearest neighbour and minimum spanning tree deletion) taught in D2. The question requires careful execution of well-defined algorithms with multiple arithmetic steps, but no problem-solving insight or novel reasoning—just methodical application of textbook techniques to a 7-vertex network. |
| 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 | G | |
| A | \(-\) | 83 | 57 | 68 | 103 | 91 | 120 |
| B | 83 | \(-\) | 78 | 63 | 41 | 82 | 52 |
| C | 57 | 78 | \(-\) | 37 | 59 | 63 | 74 |
| D | 68 | 63 | 37 | \(-\) | 60 | 52 | 62 |
| E | 103 | 41 | 59 | 60 | \(-\) | 48 | 51 |
| F | 91 | 82 | 63 | 52 | 48 | \(-\) | 77 |
| G | 120 | 52 | 74 | 62 | 51 | 77 | \(-\) |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | B | BF |
| Answer | Marks |
|---|---|
| C | CF |
| Answer | Marks |
|---|---|
| D | DF |
| Answer | Marks |
|---|---|
| E | EF |
Question 3:
3 | B | BF
BG
BH
C | CF
CH
D | DF
DH
E | EF
EG
EHThis question should be answered on the sheet provided.
The table below gives distances, in miles, for a network relating to a travelling salesman problem.
\begin{tabular}{c|ccccccc}
& A & B & C & D & E & F & G \\
\hline
A & $-$ & 83 & 57 & 68 & 103 & 91 & 120 \\
B & 83 & $-$ & 78 & 63 & 41 & 82 & 52 \\
C & 57 & 78 & $-$ & 37 & 59 & 63 & 74 \\
D & 68 & 63 & 37 & $-$ & 60 & 52 & 62 \\
E & 103 & 41 & 59 & 60 & $-$ & 48 & 51 \\
F & 91 & 82 & 63 & 52 & 48 & $-$ & 77 \\
G & 120 & 52 & 74 & 62 & 51 & 77 & $-$ \\
\end{tabular}
\begin{enumerate}[label=(\alph*)]
\item Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of a tour beginning and ending at A and state the tour. [4 marks]
\item By deleting A, obtain a lower bound for the length of a tour. [4 marks]
\item Hence, write down an inequality which must by satisfied by d, the minimum distance travelled in miles. [1 mark]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q3 [9]}}