Nearest neighbour algorithm
From Wikipedia, the free encyclopedia
- This article is about an approximation algorithm to solve the travelling salesman problem. For other uses, see nearest neighbor.
The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. It does not in general compute the optimal result.
These are the steps of the algorithm:
- Pick an arbitrary starting vertex.
- If the current vertex has no unmarked edges, terminate.
- Find the unmarked edge from the current vertex with the least weight and mark it.
- Select the vertex at the other end of the edge.
- Repeat from step 2.
The order in which the vertices are visited is the output of the algorithm.
The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight. The result 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.