Nearest Neighbor Heuristic
The nearest neighbor heuristic is a heuristic opening procedure from graph theory and is used, among other things, to approximate a solution to the traveling salesman problem .
Proceeding from a node as the starting point, the minimally weighted neighboring edge to the next node is selected. This is continued successively until all nodes have been combined into a Hamiltonian circle . In general, this greedy algorithm does not provide the best solution. This is mainly due to the fact that the start node and the end node are not taken into account at any point in time and instead a possible large distance between them is accepted. Indeed, examples can be constructed with solutions as far from the optimum as desired.
The method becomes better by iteratively selecting each individual node of the graph once as the starting node for determining the weighting of the respective resulting path and then comparing these with one another.
However, this all nearest neighbor heuristic already corresponds to the complexity class .
See also
Individual evidence
- ↑ Lawler, Lenstra, Rinnooy Kan, Shmoys (Eds.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization . Wiley, Chichester 1985. ISBN 0-471-90413-9 , Section 5.3.1: Nearest neighbor algorithm