Nearest neighbour algorithm

The nearest neighbor heuristic is a heuristic opening process from graph theory, and is used among other things for approximating a solution of the problem of the traveling salesman.

From one node as a starting point, starting the minimally weighted adjacent edge is elected as the next node. This is successively continued until all nodes have been combined to form a Hamiltonian cycle. In general, this greedy algorithm does not provide the best solution. This is mainly because that the start node and end node are taken into account at any time and instead a possible large distance between them is taken into account. In fact, examples can be constructed with arbitrarily far away from the optimum solutions.

By iteratively each node of the graph is once each selected as the start node to determine the weighting of the respective resulting path and these are finally compared with each other, the method is better.

However, this all nearest neighbor heuristic already corresponds to the complexity class.