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 your 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.
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.