D1.3.2 The practical and classical Travelling Salesman problems. The…
Section
D1.3 Algorithms on graphs II
Level
A level only
Statement
The practical and classical Travelling Salesman problems. The classical problem for complete graphs satisfying the triangle inequality. Determination of upper and lower bounds using minimum spanning tree methods. The nearest neighbour algorithm.
Guidance
The use of short cuts to improve upper bound is included. The conversion of a network into a complete network of shortest ‘distances’ is included.
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (c) (i) was answered well and did not rely on part (b) being correct. Errors in (ii) were typically in computing a time of 139 and not correctly reading off the distance values from the fifth iteration. However, in the final part a significant number of candidates failed to correctly interpret this cycle in terms of the actual villages visited, with many just requoting their answer to (i).
Key points from the mark scheme and examiner's report
NNA from B along rows: B–D–E–F–G–A–C–B
115 minutes (139 a common slip)
actual villages B D E F G A B D C D B
many just repeated the cycle
June 2024 · Paper 3D (Decision 1) · Q2(d)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (d) the majority of candidate realised they needed to double the weight of their minimum spanning tree to obtain the upper bound although some candidates were confused here with the method for the calculation of the lower bound and instead added ‘two shortest lengths’ or sometimes added just AD.
Key points from the mark scheme and examiner's report
initial upper bound is twice the MST: 482
some added the two shortest arcs (lower-bound method)
June 2024 · Paper 3D (Decision 1) · Q2(e)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (e), the nearest neighbour algorithm was usually successfully applied with the most common error being the omission of returning to the starting vertex or sometimes due to missing a node en route.
Key points from the mark scheme and examiner's report
NNA from D: D–E–H–J–C–B–G–F–A–D = 318 miles
must return to D
June 2024 · Paper 3D (Decision 1) · Q2(f)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In the comparison of upper and lower bounds in parts (f) and (h), it was clear that most candidates understood which would be the preferred option in either case and could clearly explain why. Some candidates were not quite specific enough though, giving explanations about the range being reduced rather than comparing the relevant values. The question was well answered overall, with most lost marks being due to slips rather than a misunderstanding of the content being assessed.
Key points from the mark scheme and examiner's report
best upper bound is the smallest: 318 (less than 352 and 482)
vague comments about reducing the range scored 0
June 2024 · Paper 3D (Decision 1) · Q2(g)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In part (g), many candidates started again, rather than adapting the work already done. Those who used their minimum spanning tree from part (a) generally made fewer errors than those
Key points from the mark scheme and examiner's report
adapt the MST: RMST = 241 − 26 = 215, plus AD 26 and AF 40 = 281
reusing the MST avoided errors
June 2024 · Paper 3D (Decision 1) · Q2(h)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
In the comparison of upper and lower bounds in parts (f) and (h), it was clear that most candidates understood which would be the preferred option in either case and could clearly explain why. Some candidates were not quite specific enough though, giving explanations about the range being reduced rather than comparing the relevant values. The question was well answered overall, with most lost marks being due to slips rather than a misunderstanding of the content being assessed.
Key points from the mark scheme and examiner's report
best lower bound is the largest: 281 > 274
June 2023 · Paper 3D (Decision 1) · Q5(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (c) was answered well by most candidates. A minority did not complete the tour by returning to G, either failing to close their tour or by returning to A. Mistakes were made in using this to calculate an upper bound some multiplying the length of the route by 2.
Key points from the mark scheme and examiner's report
NNA from G: G–A–F–D–B–C–J–H–E–G = 271 miles
must return to G
June 2023 · Paper 3D (Decision 1) · Q5(d)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Part (d) proved more challenging and was not attempted by a significant number of candidates. Very few candidates recognised how they could adapt their MST from (b) to answer (d) efficiently and instead found the RMST again (and this was often done incorrectly). This was one of the parts of the paper most likely to be left unanswered by candidates with a significant number moving on once part (c) was completed. Those candidates who found the correct RMST tended to score both marks.
Key points from the mark scheme and examiner's report
residual MST = 141 − 8 = 133 (reuse the MST from (b) without AG) + two smallest arcs at G (8 + 23) = 164
often not attempted
June 2023 · Paper 3D (Decision 1) · Q5(e)1 mark
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
For part (e) many candidates did not recognise the need to state the route in terms of the actual towns visited. Some candidates gave a partial route, quite a few wrote a sentence explaining about the need to go to each town rather than explicitly stating the route, and others gave a lengthy explanation in words which did not meet the demands of the question. Again, this part was not attempted by a large proportion of candidates.
Key points from the mark scheme and examiner's report
G A F D (via G, A) B C J H (via J) E (via J, C, B, A) G
must list the actual towns, not a description
June 2022 · Paper 3D (Decision 1) · Q3(c)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
It was the final part of this question that caused most problems for candidates. As has been noted before, many candidates failed to appreciate that the standard method of applying the nearest neighbour method on a table with undirected arcs would not apply in the same way with directed arcs. It would therefore be advisable to apply nearest neighbour using the rows rather than the corresponding columns. A few did not end their routes by returning to E or thought a diagram of their routes, with or without direction arrows, was sufficient. Almost all candidates with both correct routes were able to gain the final two marks for stating the corresponding lengths and choosing the shorter one as a better upper bound. This was an example of the importance of using correct methods on this paper, as very many candidates with incorrect routes had their lengths correct and an appropriate choice of upper bound but still could not score any marks. 5
Key points from the mark scheme and examiner's report
directed matrix so apply NNA along rows
two cycles from E (tie): E–C–D–F–A–B–E = 76 and E–F–A–B–D–C–E = 59
the smaller, 59, is the better upper bound
must return to E
Nov 2021 · Paper 3D (Decision 1) · Q3(c)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was the best answered question on the paper covering the topic of minimum connectors and the travelling salesperson problem. Most candidates correctly saw the link between finding
Key points from the mark scheme and examiner's report
NNA from J: J–F–E–C–D–H–A–B–G–J
upper bound 267 miles
must return to J
Nov 2021 · Paper 3D (Decision 1) · Q3(d)2 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
This was the best answered question on the paper covering the topic of minimum connectors and the travelling salesperson problem. Most candidates correctly saw the link between finding the MST and its weight in parts (a) and (b), and the link to the lower bound in (d).
Key points from the mark scheme and examiner's report
residual MST 183 + two smallest arcs at J (25 + 27) = 235 miles
Oct 2020 · Paper 3D (Decision 1) · Q3(c)3 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
Floyd’s algorithm is another topic new on the specification. Most candidates were Hamiltonian cycle ACBEDA in (c)(i), realising the necessity to use the nearest neighbour algorithm across rows, rather than down columns, due to the directed arc DC. The common error was cycle ACDEBA where the arc CD is incorrect. The next mark (c)(ii) was only available to those candidates with correct working In (i). Very few correct answers were seen in (iii), with some candidates misunderstanding the question and providing a description but not a route through the labelled villages.
Key points from the mark scheme and examiner's report
NNA across rows (matrix not symmetric): A–C–B–E–D–A, 22 minutes
actual route A–C–B–C–E–D–C–A
ACDEBA was the common error
interpretation rarely correct
June 2019 · Paper 3D (Decision 1) · Q3(d)4 marks
Mark scheme (whole question; this part is marked with the orange bar)
Examiner's comment
It was part (c) and (d) that caused most problems for candidates. In part (c) several candidates were able to score full marks for a near full (but not totally complete) response, due to the varying nature of the different methods. Many lost marks though as they were not clear about how to use the tables, many did not mention rows and columns specifically, which lost the first two marks in this part. Also, the second (dependent) B mark was especially rarely scored as many candidates did not fully consider the route from D to A. Meanwhile many candidates who lost these first two B marks still earnt the third for a correct route EDCA. Candidates should be aware of the level of detail required for a question that requires them to explain a method. In part (d), many candidates failed to appreciate that the standard method of applying the nearest neighbour method on a table with undirected arcs would not apply in the same way with directed arcs, so incorrectly stated the nearest neighbour route. In nearly all cases this therefore led to the rest of part (d) being incorrect so unfortunately no marks in this part was not an uncommon score. Parts (d)(iii) and (iv) proved particularly challenging with very few candidates realising that (iii) was requesting the actual route used and that (iv) required candidates to find a shorter cycle. In general, proof that a solution to any Decision Mathematics problem is non-optimal only requires a counter-example i.e. a better solution.
Key points from the mark scheme and examiner's report
NNA from D: D–E–C–B–A–D, 36 miles
actual route D–E–D–C–B–A–E–D
a cheaper cycle such as A–E–D–C–B–A = 30 proves it is not optimal
many did not interpret the cycle in terms of actual roads
Find an Edexcel Further Maths tutor
Stuck on this? Book a trial lesson with our Further Maths tutor.