Nearest neighbour algorithm
|
|
This article is about an algorithm to approximately solve the traveling salesman problem. For the machine learning algorithm, see nearest neighbor (pattern recognition).
The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the traveling salesman problem, and usually comes to within twenty percent of the optimal route. It is also a lot faster than testing every route and some other algorithms.
These are the steps of the algorithm:
- Make two sets of nodes, set A and set B, and put all nodes into set B
- Put the starting node into set A
- Pick the node which is closest to the last node which was placed in set A and is not in set A; put this closest neighbouring node into set A
- Repeat step 3 until all nodes are in set A and B is empty.
The nearest neighbour algorithm is easy to implement and can be done quickly, but it can sometimes miss shorter routes which are easily noticed with human hindsight. The results of the nearest neighbour algorithm should be checked before use, just in case such a shorter route has been missed.
In the worst case, the algorithm can compute tours that are by an arbitrary factor larger than the optimal tour. To be precise, for every constant r there is an instance of the traveling salesman problem such that the length of the tour computed by the nearest neighbour algorithm is greater than or equal to r times the length of the optimal tour.