ConceptConceptDocsDocuments

Edexcel IAL Mathematics D1.3.4 nearest neighbour algorithm

Practise nearest-neighbour routes by choosing closest unvisited vertices, recording cycles and comparing upper bounds from starts.

Syllabus
First assessment 2019
Course
Mathematics YMA01
Level
AS

Exam points

  • Apply nearest neighbour from the stated start vertex and write the full cycle with length.
  • Show alternative routes when a tie occurs, then compare their route lengths.
  • Choose the best upper bound by comparing nearest-neighbour totals from different starts.

D1.3.4 - nearest neighbour algorithm question 1

[Maximum number: 2]
Table 1

Table 1

Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound.

Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.

All question bank results loaded