The nearest neighbor algorithm, also called the nearest neighbor heuristic, is a greedy algorithm for constructing a tour in the traveling salesman problem when a distance is given between every pair of cities. Starting at a chosen city, it repeatedly visits the closest unvisited city and returns to the starting city after all cities have been visited. Ties can be resolved by a fixed ordering of the cities (Cook 2012, pp. 65-67).

The resulting Hamiltonian cycle need not be shortest, and the tour can depend on the starting city and the resolution of ties. Trying each starting city and retaining the shortest of the resulting tours can improve the result but does not guarantee an optimal tour. With precomputed distances, a straightforward implementation from one starting city uses distance comparisons for cities.

For symmetric distances satisfying the triangle inequality, the worst-case ratio of the tour length to the optimum grows logarithmically with the number of cities (Rosenkrantz et al. 1977). The algorithm is distinct from the nearest neighbor problem in computational geometry, which asks for the closest point to a specified query point rather than for a tour.

See also

Greedy Algorithm, Nearest Neighbor Problem, Traveling Salesman Problem

Explore with Wolfram|Alpha

References

Cook, W. J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton, NJ: Princeton University Press, pp. 65-67, 2012.Rosenkrantz, D. J.; Stearns, R. E.; and Lewis, P. M., II. "An Analysis of Several Heuristics for the Traveling Salesman Problem." SIAM J. Comput. 6, 563-581, 1977. https://doi.org/10.1137/0206041.

Cite this as:

Weisstein, Eric W. "Nearest Neighbor Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NearestNeighborAlgorithm.html

Subject classifications