| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Improve Upper Bound with Shortcuts |
| Difficulty | Standard +0.3 This is a standard D2 travelling salesman problem requiring routine application of three algorithmic methods (shortcut method, nearest neighbour, and lower bound via deletion). Part (a) involves simple arithmetic on a given MST with minimal decision-making about shortcuts. The question is methodical but requires no novel insight—just careful execution of learned procedures, making it slightly easier than average A-level maths. |
| 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 | - | 122 | 217 | 137 | 109 | 82 |
| B | 122 | - | 110 | 130 | 128 | 204 |
| C | 217 | 110 | - | 204 | 238 | 135 |
| D | 137 | 130 | 204 | - | 98 | 211 |
| E | 109 | 128 | 238 | 98 | - | 113 |
| F | 82 | 204 | 135 | 211 | 113 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Part (a) | If use CD as shortcut get 807 or if use CF + AD get 793 | M1, A1 |
| (2) | a1A1: CAO – shortcut and length must be consistent | |
| Part (b) | \(A \quad F \quad E \quad D \quad B \quad C \quad A\) | B1 |
| \(82 + 113 + 98 + 130 + 110 + 217 = 750\) | B1 | |
| (2) | ||
| Part (c) | Length of RMST = 439 | B1 |
| \(439 + 82 + 113 = 634\) | M1, A1 | c1M1: Adding two least weighted arcs to their RMST length |
| (3) | c1A1: CAO | |
| Part (d) | \(634 < \text{optimal} \leq 750\) | B1ft |
| (1) | ||
| Total | 8 marks |
| **Part (a)** | If use CD as shortcut get 807 or if use CF + AD get 793 | M1, A1 | a1M1: Their plausible shortcut leading to a value $< 810$ and a length below 810 stated |
|---|---|---|---|
| | | **(2)** | a1A1: CAO – shortcut and length must be consistent |
| **Part (b)** | $A \quad F \quad E \quad D \quad B \quad C \quad A$ | B1 | |
| | $82 + 113 + 98 + 130 + 110 + 217 = 750$ | B1 | |
| | | **(2)** | |
| **Part (c)** | Length of RMST = 439 | B1 | |
| | $439 + 82 + 113 = 634$ | M1, A1 | c1M1: Adding two least weighted arcs to their RMST length |
| | | **(3)** | c1A1: CAO |
| **Part (d)** | $634 < \text{optimal} \leq 750$ | B1ft | d1B1: An interval that incorporates their lower bound from (c) and their best upper bound from either (a) or (b) |
| | | **(1)** | |
| **Total** | | **8 marks** | |
---2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F \\
\hline
A & - & 122 & 217 & 137 & 109 & 82 \\
\hline
B & 122 & - & 110 & 130 & 128 & 204 \\
\hline
C & 217 & 110 & - & 204 & 238 & 135 \\
\hline
D & 137 & 130 & 204 & - & 98 & 211 \\
\hline
E & 109 & 128 & 238 & 98 & - & 113 \\
\hline
F & 82 & 204 & 135 & 211 & 113 & - \\
\hline
\end{tabular}
\end{center}
Liz must visit each town at least once. She will start and finish at A and wishes to minimise the total distance she will travel.
\begin{enumerate}[label=(\alph*)]
\item Starting with the minimum spanning tree given in your answer book, use the shortcut method to find an upper bound below 810 km for Liz's route. You must state the shortcut(s) you use and the length of your upper bound.\\
(2)
\item Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Liz's route.
\item Starting by deleting F , and all of its arcs, find a lower bound for the length of Liz's route.
\item Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2013 Q2 [8]}}