Algorithm of the nearest neighbor in the traveling salesman problem

The nearest neighbor algorithm is one of the simplest heuristic algorithms for solving the traveling salesman problem . Belongs to the category of "greedy" algorithms .

It is formulated as follows:

The rounds of the plan are sequentially included in the route, and each next included point must be closest to the last selected point among all the others not yet included in the route.

The algorithm is simple to implement, it is quickly executed, but, like other "greedy" algorithms, it can produce non-optimal solutions. One of the heuristic criteria for evaluating a solution is the rule: if the path traversed in the last steps of the algorithm is comparable to the path traversed in the initial steps, then we can conditionally consider the route found acceptable, otherwise, there are probably more optimal solutions. Another way to evaluate the solution is to use the lower bound algorithm.

For any number of cities greater than three, in the traveling salesman problem, it is possible to choose such an arrangement of cities (the value of the distance between the vertices of the graph and the indication of the initial vertex) that the nearest neighbor algorithm will produce the worst solution. ^[one]