Jump to content

Nearest neighbour algorithm

From Simple English Wikipedia, the free encyclopedia

Nearest neighbour algorithms is a the name given to a number of greedy algorithms to solve problems related to graph theory. This algorithm was made to find a solution to the travelling salesman problem. In general, these algorithms try to find a Hamlitonian cycle as follows:

  1. Start at some vertex, and mark it as current.
  2. From the current vertex, take the shortest 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.