Edexcel IAL - Decision Mathematics 1- 3.4 Nearest Neighbour Algorithm- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 3.4 Nearest Neighbour Algorithm -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 3.4 Nearest Neighbour Algorithm -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 3.4 Nearest Neighbour Algorithm
The Nearest Neighbour Algorithm
The nearest neighbour algorithm is a simple method used to find a short travelling salesman route in a network.
It is mainly used to obtain a quick upper bound for the Travelling Salesman Problem (TSP), rather than to guarantee the shortest possible tour.
When the Algorithm is Used
- for practical travelling salesman problems
- to obtain an initial tour for the classical TSP
- to give an upper bound that can later be improved using shortcuts
Basic Idea
At each step, the algorithm moves to the nearest unvisited vertex.
Once all vertices have been visited, the route returns to the starting vertex.
Step-by-Step Description
The algorithm proceeds as follows:
- Step 1: Choose a starting vertex
- Step 2: Travel to the nearest unvisited vertex
- Step 3: Mark the vertex as visited
- Step 4: Repeat Steps 2 and 3 until all vertices are visited
- Step 5: Return to the starting vertex to complete the tour
Key Properties
- The route depends on the chosen starting vertex
- The algorithm is greedy, making locally optimal choices
- It does not always produce the shortest possible tour
- It is fast and easy to apply by hand
Advantages
- Simple and quick to use
- Provides a reasonable upper bound
- Useful as a starting point for further improvements
Disadvantages
- May give a poor route depending on the start vertex
- Can become trapped into making early bad choices
- Does not guarantee an optimal solution
Important Examination Notes
- All distances must be clearly shown
- The order of visiting vertices should be stated
- The final tour length must be calculated
- The result should be identified as an upper bound
Example
Four cities A, B, C and D form a complete network with distances:
AB = 6, AC = 4, AD = 7, BC = 5, BD = 3, CD = 6
Starting at A, use the nearest neighbour algorithm to find a travelling salesman route and its length.
▶️ Answer / Explanation
Step 1: Start at A
Nearest unvisited vertex: C (distance 4)
Step 2: From C
Nearest unvisited vertex: B (distance 5)
Step 3: From B
Nearest unvisited vertex: D (distance 3)
Step 4: All vertices visited, return to A
DA = 7
Route:
A → C → B → D → A
Total length:
\( \mathrm{4 + 5 + 3 + 7 = 19} \)
Conclusion:
The nearest neighbour algorithm gives an upper bound of \( \mathrm{19} \).
Example
Four cities A, B, C and D form a complete network with distances:
AB = 6, AC = 4, AD = 7, BC = 5, BD = 3, CD = 6
Using the same network , apply the nearest neighbour algorithm starting at B.
▶️ Answer / Explanation
Step 1: Start at B
Nearest unvisited vertex: D (distance 3)
Step 2: From D
Nearest unvisited vertex: A (distance 7)
Step 3: From A
Nearest unvisited vertex: C (distance 4)
Step 4: All vertices visited, return to B
CB = 5
Route:
B → D → A → C → B
Total length:
\( \mathrm{3 + 7 + 4 + 5 = 19} \)
Conclusion:
Starting at a different vertex gives a different route but the same upper bound of \( \mathrm{19} \).
Example
A classical TSP has five cities. Using the nearest neighbour algorithm, a tour of length \( \mathrm{42} \) is found.
The minimum spanning tree of the network has total weight \( \mathrm{28} \).
State suitable upper and lower bounds for the shortest travelling salesman tour.
▶️ Answer / Explanation
Lower bound:
The weight of the minimum spanning tree gives:
\( \mathrm{28} \)
Upper bound:
The nearest neighbour tour gives:
\( \mathrm{42} \)
Conclusion:
The true shortest travelling salesman route lies between \( \mathrm{28} \) and \( \mathrm{42} \).