Encyclopedia > Nearest neighbour algorithm

  Article Content

Nearest neighbour algorithm

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:

  1. Make two sets of nodes, set A and set B, and put all nodes into set B
  2. Put your starting node into set A
  3. 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
  4. 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Grateful Dead

... two-track mixes made at the time of the recording. There have been at least 28 DP releases as of April 2003. Then a series of videos began to trickle out of "The Vault" ...

 
 
 
This page was created in 24.6 ms