Nearest-Neighbor Route Extension¶
Construction heuristic — instantiates Greedy Stepwise Commitment
Grows a path by repeatedly stepping to the nearest still-available point, letting the current endpoint alone decide the next move.
Nearest-Neighbor Route Extension builds a route the simplest way imaginable: stand at the current endpoint, look at the points not yet visited, step to the closest one, and repeat until none remain. The one idea that makes it this mechanism is that the entire live state collapses to a single endpoint plus a visited set — the next candidate set and the score that ranks it are both defined relative to where you happen to be standing now. It never consults a plan of the whole route; each step is a purely local reach for the nearest thing.
Example¶
A circuit-board drilling machine must punch a few hundred holes and wants to move its head as little as possible. Nearest-Neighbor Route Extension drives it: from the hole just drilled, it finds the nearest hole not yet drilled, moves there, drills, and repeats. Starting near one corner, the head sweeps neatly through dense clusters, drilling each local pocket of holes before moving on — fast to compute and, for most of the board, genuinely tight.
The catch shows up at the end. Because every step only ever grabbed the nearest remaining hole, the last few holes are whatever got skipped along the way — often scattered far apart — so the tour closes with one or two long, wasteful traverses back across the board. The route is good locally at every step and merely acceptable as a whole, which is exactly the signature of the method.
How it works¶
- Reduce the partial solution to its current endpoint and the set of visited points; nothing else about the path so far is consulted.
- Generate the feasible next steps as the unvisited points reachable from that endpoint, and pick the nearest under the chosen distance metric.
- Move, mark the point visited, and recompute "nearest" from the new endpoint. What distinguishes it from generic greedy is that both the candidate set and the score are re-anchored to the endpoint at every step, so the same point is "near" or "far" depending only on where the path currently ends.
Tuning parameters¶
- Distance metric — Euclidean, travel-time, or a cost that folds in turn penalties or one-way constraints; changing it changes what "nearest" means.
- Start point — where the path begins; a poor start can strand distant points for the end. Restarting from several starts and keeping the best tour is the cheapest quality lever.
- Candidate restriction — considering only the k nearest unvisited points speeds each step on large instances at the risk of missing a better reach.
- Closure — whether the route must return to its origin (a tour) or may end anywhere (an open path); tours pay the notorious final return leg.
When it helps, and when it misleads¶
Its strength is speed and simplicity: near-linear effort per step, no lookahead, and results that are perfectly good when points fall in tight clusters or when a quick first draft is all that is needed.
Its failure mode is structural, not incidental. Stepping to the locally nearest point does not compose into a globally short route — the method bets that it will, and that bet is famously weak: for the traveling-salesman setting the tour it returns can be arbitrarily worse than optimal as instances grow, precisely because early greed leaves stranded points that force long closing legs.[n1] The classic misuse is to treat its output as the answer rather than a starting point. The discipline is to follow it with a local-improvement pass (such as 2-opt) or multi-start, and to read the tour as a construction, not an optimum.
How it implements the components¶
decision_state_representation— the whole path is compressed to its current endpoint plus the visited set; that compact state is what makes "nearest to here" well defined.feasible_next_step_generator— the candidates are exactly the unvisited points reachable from the endpoint, regenerated after every move.local_global_fit_assumption— it stakes everything on the (often false) premise that a chain of locally nearest steps yields a globally short route.
It does not rank by a criteria hierarchy — that selection logic is Lexicographic Priority Rule — nor maintain a re-prioritizing candidate engine (Priority-Queue Step Selection); repairing the traps it leaves belongs to Trap-Sentinel Escalation.
Related¶
- Instantiates: Greedy Stepwise Commitment — a domain-specific greedy construction for path and tour problems.
- Sibling mechanisms: Trap-Sentinel Escalation · Priority-Queue Step Selection · Lexicographic Priority Rule · Sorted Candidate Sweep · Shortest-Processing-Time-First Rule · Dijkstra-Style Frontier Expansion · Earliest-Deadline-First Dispatch · Highest-Marginal-Gain-First Rule · Greedy Assignment Pass · Greedy Set-Cover Heuristic · Kruskal-Style Edge Acceptance
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: The mechanism repeatedly computes feasible unvisited points, scores their distance from the current endpoint, and greedily extends the route to the nearest.
Nearest alternative: Control, Automation & Runtime — It iterates as the endpoint changes, but it constructs an optimized path rather than actuating a live operational system.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Single lineage
Present-day reach: Multi-domain
Rationale: The rule is the classical nearest-neighbor heuristic for routing and the traveling-salesman problem in combinatorial optimization.
Related originating lineages:
- Computer Science & Software Engineering — Algorithm-design practice formalized and analyzed the greedy implementation and approximation behavior.
Review resolution: Both independent reviews agree on primary origin operations_research; reconciliation resolves alternate_origin_disagreement. Formative alternate lineages retained: computer_science. The broader reach of later applications is kept separate as domain_reach=multi_domain; origin_mode=single_lineage describes the historical relationship among lineages. Confidence is conservatively reconciled to high, and encyclopedia_synthesis=false preserves the reviewers' boundary judgment.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
Nearest-Neighbor Route Extension is a construction heuristic: it exists to produce a decent initial route quickly, on the understanding that a repair step will improve it. That is why it pairs naturally with Trap-Sentinel Escalation and local-search repair rather than standing alone as a final answer.
[n1] The nearest-neighbor heuristic for the traveling-salesman problem has an approximation ratio that grows with instance size rather than staying within a constant factor of optimal — a standard textbook result and the canonical illustration that locally shortest steps need not compose into a globally short tour. ↩