| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2020 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Improve Upper Bound with Shortcuts |
| Difficulty | Standard +0.3 This is a standard D1 travelling salesman problem requiring three routine algorithmic procedures (shortcut method, nearest neighbour, and lower bound via deletion). Each part follows a mechanical process taught directly in the specification with no novel problem-solving required. The calculations are straightforward and the question structure is typical of D1 exam questions, making it slightly easier than average overall. |
| 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 | - | 57 | 76 | 59 | 72 | 65 |
| B | 57 | - | 67 | 80 | 66 | 76 |
| C | 76 | 67 | - | 71 | 83 | 80 |
| D | 59 | 80 | 71 | - | 77 | 78 |
| E | 72 | 66 | 83 | 77 | - | 69 |
| F | 65 | 76 | 80 | 78 | 69 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| (a) e.g. add CD and remove AD, BA and BC gives 516 (km); e.g. add EF and remove EB, BA and AF gives 509 (km) | M1 A1 (2) | a1M1: Must clearly start with 2(length of given MST) and add and subtract at least one arc (to give a network of weight < 628) – graph must be connected and Eulerian. a1A1: CAO – shortcut(s) and length must be consistent (with length stated < 520). The shortcuts must be clearly stated (that is the arcs added and subtracted) and network must be connected and Eulerian. |
| (b) NNA: \(A – B – E – F – D – C – A\); 57 66 69 78 71 76 = 417 (km) | B1 B1 (2) | b1B1: CAO (must return to A) – must be stated in terms of either the nodes or arcs (e.g. AB, BE, EF,…) but not just the weights of the arcs. b2B1: CAO (417). |
| (c) Length of RMST = 248; 248 + 66 + 69 = 383 (km) | M1 A1 (3) 7 marks | c1B1: Correct length of RMST (248) – maybe implied by later working. c1M1: Adding the two correct least weighted arcs (66 and 69) to their RMST length (231 ≤ length ≤ 265) – give bod but their RMST must only contain 4 arcs – this mark can be implied by the correct value for the lower bound. c1A1: CAO (383) – if correct answer with no working then award B0M1A1. |
| Answer | Marks | Guidance |
|--------|-------|----------|
| (a) e.g. add CD and remove AD, BA and BC gives 516 (km); e.g. add EF and remove EB, BA and AF gives 509 (km) | M1 A1 (2) | a1M1: Must clearly start with 2(length of given MST) and add and subtract at least one arc (to give a network of weight < 628) – graph must be connected and Eulerian. a1A1: CAO – shortcut(s) and length must be consistent (with length stated < 520). The shortcuts must be clearly stated (that is the arcs added and subtracted) and network must be connected and Eulerian. |
| (b) NNA: $A – B – E – F – D – C – A$; 57 66 69 78 71 76 = 417 (km) | B1 B1 (2) | b1B1: CAO (must return to A) – must be stated in terms of either the nodes or arcs (e.g. AB, BE, EF,…) but not just the weights of the arcs. b2B1: CAO (417). |
| (c) Length of RMST = 248; 248 + 66 + 69 = 383 (km) | M1 A1 (3) 7 marks | c1B1: Correct length of RMST (248) – maybe implied by later working. c1M1: Adding the two correct least weighted arcs (66 and 69) to their RMST length (231 ≤ length ≤ 265) – give bod but their RMST must only contain 4 arcs – this mark can be implied by the correct value for the lower bound. c1A1: CAO (383) – if correct answer with no working then award B0M1A1. |
---3. The table below 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 & - & 57 & 76 & 59 & 72 & 65 \\
\hline
B & 57 & - & 67 & 80 & 66 & 76 \\
\hline
C & 76 & 67 & - & 71 & 83 & 80 \\
\hline
D & 59 & 80 & 71 & - & 77 & 78 \\
\hline
E & 72 & 66 & 83 & 77 & - & 69 \\
\hline
F & 65 & 76 & 80 & 78 & 69 & - \\
\hline
\end{tabular}
\end{center}
Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.
\begin{enumerate}[label=(\alph*)]
\item Starting with the minimum spanning tree in the answer book, use the shortcut method to find an upper bound below 520 km for Mei's route. You must state the shortcut(s) you use and the length of your upper bound.
\item Use the nearest neighbour algorithm, starting at A , to find another upper bound for the length of Mei's route.
\item Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei's route. Make your method clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2020 Q3 [7]}}