Nearest neighbour algorithm
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:
- Start at some vertex, and mark it as current.
- From the current vertex, take the shortest edge that connects it to an unvisited vertex V.
- Set the current vertex to V.
- If there no unvisited vertices left, you are done.
- 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.
