Nearest neighbour algorithm

related topics
{math, number, function}
{album, band, music}
{line, north, south}
{country, population, people}
{math, energy, light}
{city, population, household}

The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. It quickly yields a short tour, but usually not the optimal one.

Below is the application of nearest neighbour algorithm on TSP

These are the steps of the algorithm:

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 there are much better tours. Another check is to use an algorithm such as the lower bound 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 length 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[1].


See also


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.

Full article ▸

related documents
LALR parser
Contraction mapping
Best-first search
Blum Blum Shub
Lyapunov fractal
Complete measure
Normal morphism
Axiom of union
Sophie Germain prime
Baire category theorem
Group homomorphism
Composite number
Partition of unity
Linear congruence theorem
Mutual recursion
Multiple inheritance
Characteristic subgroup
Permutation group
Up to
Hamiltonian path problem
Complete category
Category of sets
Tree structure
Zhu Shijie
AVL tree
Elias delta coding
Chosen-plaintext attack
Brun's constant