Nearest Neighbour Algorithm

The nearest neighbour algorithm is one of the earliest algorithms used to find an approximate solution to the travelling salesman problem. Starting from an arbitrary city, it repeatedly travels to the closest unvisited city until every city has been visited, which makes it simple to implement and fast to run. Its solutions are often poor: because each step is chosen greedily without regard for the overall route, the algorithm can miss shorter tours that are easy for a person to spot, its worst-case tour length can be arbitrarily longer than the true optimum, and in some cases it can fail to produce a feasible tour at all. A common way to judge whether a better tour is available is to compare the lengths of the early and late segments of the route: when the later segments are much longer than the earlier ones, a better solution usually exists. This entity is distinct from the k-nearest neighbors algorithm used in machine learning classification, which solves a different problem. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/