Nearest neighbour algorithm

Greedy nearest neighbour for routing

As a constructive heuristic for problems in graph theory and routing, the nearest neighbour method starts from a chosen vertex and repeatedly selects the shortest edge from the current vertex to any not‑yet‑visited vertex. In the context of the travelling salesman problem this yields a tour (when the graph is complete) by visiting each node once and returning to the start. The algorithm is an instance of simple greedy algorithms: it makes the locally best choice at each step without backtracking.

Typical procedure:

• Choose a start vertex and mark it current.
• From the current vertex, pick the nearest unvisited vertex and move there.
• Mark that vertex visited and repeat until all vertices are visited.
• Return to the start to close the tour (if required by the problem).

Strengths include ease of implementation and low overhead; naive implementations run in O(n^2) time for n nodes. Weaknesses are significant: the greedy choice does not guarantee optimality, and on specially constructed instances the produced tour can be much worse than the optimum. If the input graph is not complete the procedure can also become stuck on a vertex with no unvisited neighbours.

Nearest neighbour in classification and search

In machine learning, "nearest neighbour" usually refers to k‑nearest neighbour (k‑NN) classifiers or regressors. The method stores examples labeled with outputs; to classify a new point it finds the k closest stored examples under some distance metric (e.g., Euclidean, Manhattan), and predicts by majority vote (classification) or by averaging (regression). k‑NN is a lazy, nonparametric method: it has no explicit training phase beyond storing the data, and prediction cost is dominated by nearest neighbour search.

Practical considerations include the choice of k, the distance metric, and data preprocessing (feature scaling, handling categorical features). Small k makes the method sensitive to noise; large k smooths decisions but can blur class boundaries. High dimensionality degrades performance because distances become less informative (the "curse of dimensionality").

Data structures, variants and applications

Efficient nearest neighbour search uses spatial data structures and approximate methods. Common exact structures include KD‑trees and ball trees, which accelerate queries in low to moderate dimensions. For very high dimensions or extremely large datasets, approximate techniques such as locality‑sensitive hashing (LSH) trade accuracy for speed. Weighted variants of k‑NN give nearer neighbours greater influence; other extensions include metric learning to adapt distances and cross‑validated selection of k.

Applications span route planning and heuristic solvers for optimization problems, pattern recognition, recommendation systems, anomaly detection, and information retrieval. Because the core idea is so general—selecting items by proximity—nearest neighbour methods appear in many algorithmic toolkits.

Limitations and practical advice

• Greedy nearest neighbour heuristics are fast and simple but do not guarantee optimality; their worst‑case performance worsens with problem size on certain instances.
• k‑NN classifiers are intuitive and effective with enough representative data, but require careful feature scaling and can be slow at query time without indexing.
• Evaluate choices (start vertex, k, distance metric, search structure) empirically and consider hybrid approaches: use nearest neighbour heuristics as initial solutions for more powerful optimizers, or combine approximate search with exact refinement.

Together, the different nearest neighbour methods illustrate a recurring tradeoff in algorithm design: locality and simplicity versus global optimality and scalability. For further technical details and implementations consult specialized texts or algorithm libraries that cover routing heuristics, spatial indexes, and instance‑based learning algorithms.