The nearest neighbor algorithm is a commonly used algorithm in directing a salesman to choose the next nearest city for him to visit. More often than not, salesmen would want to cover a greater distance since this presents more opportunities for them to sell. But the problem is they could not accomplish this, given the time, traffic and availability of resources. Thus, they have to choose which cities they could only accomplish for the day which leads them to use the nearest neighbor algorithm.
It’s a constructive heuristic algorithm that is used to solve the travelling salesman problem. The algorithm was designed to provide the shortest possible route wherein the salesman gets to visit each city at least once before he returns to his home city. It works this way. It plots the nearest city the salesman has yet to visit. For a total number of cities, the algorithm is run to identify the path that is the fastest. But unlike other algorithms, this sequence for the nearest neighbor takes into consideration the opportunities presented by other nearby cities, not just the shortest. Rather, it considers the areas that give it the most opportunities. The algorithm is, thus, programmed to identify an average route that is at least 25% longer than the shortest available route. This allows the salesman to cover more cities in a shorter time.
But that’s also where the problem lies. There are times when the algorithm fails to take into account specially arranged cities. As a result, it tends to produce the worse possible route. It’s the reason why nearest neighboring algorithm is also referred to as the greedy algorithm. In its goal to accommodate more cities in the shortest amount of time, it provides the worse results. In the end, it fails to solve the travelling salesman problem.
The Wonderful World of Algorithms 