The nearest neighbour algorithm was one of the first
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s used to solve the
travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
approximately. In that problem, the salesman starts at a random city and repeatedly visits the nearest city until all have been visited. The algorithm quickly yields a short tour, but usually not the optimal one.
Algorithm
These are the steps of the algorithm:
# Initialize all vertices as unvisited.
# Select an arbitrary vertex, set it as the current vertex u. Mark u as visited.
# Find out the shortest edge connecting the current vertex u and an unvisited vertex v.
# Set v as the current vertex u. Mark v as visited.
# If all the vertices in the domain are visited, then terminate. Else, go to step 3.
The sequence of the visited vertices is the output of the algorithm.
The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that much better tours exist. Another check is to use an algorithm such as the
lower bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an elemen ...
algorithm to estimate if this tour is good enough.
In the worst case, the algorithm results in a tour that is much longer than the optimal tour. To be precise, for every constant r there is an instance of the traveling salesman problem such that the length of the tour computed by the nearest neighbour algorithm is greater than r times the length of the optimal tour. Moreover, for each number of cities there is an assignment of distances between the cities for which the nearest neighbor heuristic produces the unique worst possible tour. (If the algorithm is applied on every vertex as the starting vertex, the best path found will be better than at least N/2-1 other tours, where N is the number of vertices.)
[G. Gutin, A. Yeo and A. Zverovich, 2002]
The nearest neighbour algorithm may not find a feasible tour at all, even when one exists.
Notes
References
* G. Gutin, A. Yeo and A. Zverovitch, Exponential Neighborhoods and Domination Analysis for the TSP, in The Traveling Salesman Problem and Its Variations, G. Gutin and A.P. Punnen (eds.), Kluwer (2002) and Springer (2007).
* G. Gutin, A. Yeo and A. Zverovich
Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP Discrete Applied Mathematics 117 (2002), 81–86.
* J. Bang-Jensen, G. Gutin and A. Yeo
When the greedy algorithm fails Discrete Optimization 1 (2004), 121–127.
* G. Bendall and F. Margot
Greedy Type Resistance of Combinatorial Problems Discrete Optimization 3 (2006), 288–298.
{{DEFAULTSORT:Nearest Neighbour Algorithm
Travelling salesman problem
Approximation algorithms
Heuristic algorithms
Graph algorithms