| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Nearest Neighbour Algorithm |
| Difficulty | Moderate -0.5 This is a standard D2 travelling salesman problem application with routine algorithmic procedures (nearest neighbour, lower bound by deletion). Part (a) requires recognizing the TSP structure (straightforward), parts (b-d) involve applying textbook algorithms to a small 5-node problem with clear instructions. The calculations are tedious but methodical with no novel insight required, making it slightly easier than average A-level difficulty. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method |
| To | |||||
| \cline{2-6} \multicolumn{1}{c|}{Time} | \(B\) | \(C\) | \(D\) | \(F\) | \(T\) |
| \(B\) | -- | 108 | 150 | 64 | 100 |
| \(C\) | 108 | -- | 54 | 104 | 60 |
| From \(D\) | 150 | 54 | -- | 150 | 102 |
| \(F\) | 64 | 104 | 150 | -- | 68 |
| \(T\) | 100 | 60 | 102 | 68 | -- |
| Monday | Tuesday | Wednesday | Thursday | Friday |
| \(B\) | \(C\) | \(D\) | \(F\) | \(T\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Use nearest neighbour B F T C D B, 64 + 68 + 60 + 54 + 150 = 396 minutes (67 hours), M1 each vertex visited once – either NN or 2 x mst-shortcut (BD), A1 cao incl return to B (BFTCDB), A1 cao (396) | M1 A1 A1 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: CT, TF, CD (Prim or Kruskal), 182 + 64 + 100 = 346 minutes, M1 Finding correct minimum spanning tree (maybe implicit) 182 sufficient, A1 cao tree or 182, M1 adding 2 least arcs to B i.e. 100 and 64 only, A1 cao ft from their m.s.t. value i.e. 164 and their tree length | M1 A1 M1 A1ft | 4 |
## Part (c)
**Answer:** Use nearest neighbour B F T C D B, 64 + 68 + 60 + 54 + 150 = 396 minutes (67 hours), M1 each vertex visited once – either NN or 2 x mst-shortcut (BD), A1 cao incl return to B (BFTCDB), A1 cao (396) | M1 A1 A1 | 3
## Part (d)
**Answer:** CT, TF, CD (Prim or Kruskal), 182 + 64 + 100 = 346 minutes, M1 Finding correct minimum spanning tree (maybe implicit) 182 sufficient, A1 cao tree or 182, M1 adding 2 least arcs to B i.e. 100 and 64 only, A1 cao ft from their m.s.t. value i.e. 164 and their tree length | M1 A1 M1 A1ft | 4
---A college wants to offer five full-day activities with a different activity each day from Monday to Friday. The sports hall will be used for these activities. Each evening the caretaker will prepare the hall by putting away the equipment from the previous activity and setting up the hall for the activity next day. On Friday evening he will put away the equipment used that day and set up the hall for the following Monday.
The 5 activities offered are Badminton ($B$), Cricket nets ($C$), Dancing ($D$), Football coaching ($F$) and Tennis ($T$). Each will be on the same day from week to week.
The college decides to offer the activities in the order that minimises the total time the caretaker has to spend preparing the hall each week.
The hall is initially set up for Badminton on Monday.
The table below shows the time, in minutes, it will take the caretaker to put away the equipment from one activity and set up the hall for the next.
\begin{tabular}{c|c|c|c|c|c|}
\multicolumn{1}{c}{} & \multicolumn{5}{c}{To} \\
\cline{2-6}
\multicolumn{1}{c|}{Time} & $B$ & $C$ & $D$ & $F$ & $T$ \\
\hline
$B$ & -- & 108 & 150 & 64 & 100 \\
\hline
$C$ & 108 & -- & 54 & 104 & 60 \\
\hline
From $D$ & 150 & 54 & -- & 150 & 102 \\
\hline
$F$ & 64 & 104 & 150 & -- & 68 \\
\hline
$T$ & 100 & 60 & 102 & 68 & -- \\
\hline
\end{tabular}
\begin{enumerate}[label=(\alph*)]
\item Explain why this problem is equivalent to the travelling salesman problem. [2]
\item Find the total time taken by the caretaker each week using this ordering.
A possible ordering of activities is
\begin{tabular}{|c|c|c|c|c|}
\hline
Monday & Tuesday & Wednesday & Thursday & Friday \\
\hline
$B$ & $C$ & $D$ & $F$ & $T$ \\
\hline
\end{tabular}
[2]
\item Starting with Badminton on Monday, use a suitable algorithm to find an ordering that reduces the total time spent each week to less than 7 hours. [3]
\item By deleting $B$, use a suitable algorithm to find a lower bound for the time taken each week. Make your method clear. [4]
\end{enumerate}
(Total 11 marks)
\hfill \mbox{\textit{Edexcel D2 2006 Q3 [11]}}