Nearest neighbour algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Nearest neighbour algorithms is a the name given to a number of greedy algorithms to solve problems related to graph theory. In general, these algorithms try to find a Hamlitonian cycle as follows:

  1. Start at some vertex, at mark it as current.
  2. From the current vertex, take the shrtest edge that connects it to an unvisited vertex V.
  3. Set the current vertex to V.
  4. If there no unvisited vertices left, you are done.
  5. Else, go to step 2.

Such algorithms are easy to implement, but they do not always find the best solution. What is worse, the algorithm may not find a tour even if one exists.