Nearest Neighbor (Heuristic)

Related Problems: TSP Type: Constructive Algorithm Work on: Graph Complexity:O(n^2)
Description: A weighted graph heuristic, always choose to visit the nearest neighbor.

Pseudo code:
1. Select a random city.
2. Find the nearest unvisited city and go there.
3. Are there any unvisitied cities left? If yes, repeat step 2.
4. Return to the first city.

The Nearest Neighbor algorithm will often keep its tours within 25% of the Held-Karp lower bound.