Starting-Vertex Choice And Tie-Breaking In Nearest Neighbor

Why Starting Points and Ties Matter

The nearest-neighbor method builds a traveling-salesperson tour by repeatedly going to a closest vertex that has not yet been visited, then returning to the starting vertex after all vertices have been visited. The local choice is simple, but it can steer the route toward a costly final return. Different starting vertices can therefore produce different tours. If two unvisited vertices are equally close, different tie-breaking choices can also change the result.

Throughout, a TSP instance is a finite complete undirected graph \(G=(V,E)\), with \(n=|V|\ge 3\), and a positive cost \(w(uv)=w(vu)\) assigned to each edge \(uv\). A tour is a cycle that visits every vertex exactly once before returning to its start. Its cost is the sum of the costs of its edges, including the return edge. We compare the tours produced by nearest-neighbor runs; choosing the cheapest among them does not by itself prove that this tour is globally optimal.

There are two ways to compare runs. With a fixed deterministic tie-breaking rule, perform one run from each start vertex and compare the \(n\) resulting tours. If ties are to be explored rather than settled by one rule, consider all permitted choices at tied steps, from each start, and compare every resulting tour. The second procedure can produce more candidates; in either case, “best” means least cost among the candidates actually considered.

Why a Run Produces a Tour

Proof. Fix a start vertex \(s\). Initially, \(s\) has been visited. Suppose the run has visited \(k\) distinct vertices, where \(1\le k<n\). At least one vertex remains unvisited. Completeness means that the current vertex is adjacent to every unvisited vertex, so the run can choose an edge to one of them. Its next vertex is unvisited, so the number of distinct visited vertices increases from \(k\) to \(k+1\). Repeating this step visits \(n\) distinct vertices. The graph is complete, so an edge joins the last vertex to \(s\); taking it closes the route. The route visits every vertex exactly once before this return and has at least three vertices, so it is a tour. \(\square\)

This proposition justifies the construction, not its quality: nearest-neighbor choices are locally cheapest among the currently available edges, but the proposition gives no guarantee that the resulting tour has minimum possible cost.

Tie-Breaking Can Change the Tour

A tie is local to a particular step: two or more unvisited vertices have the same minimum edge cost from the current vertex. A rule that always chooses the lowest-labelled vertex, for instance, makes a run reproducible, but it does not compare the other choices that were tied. To see the effect of exploring a tie, compare the possible continuations explicitly.

When a run has several tied steps, a choice at one step can change which vertices are available at the next step. To examine every outcome, branch at each tied step and continue each branch until it completes a tour. If a single deterministic tie-breaking rule is used instead, the result is one tour per starting vertex, not an evaluation of all possible tie resolutions.

Restarting at Every Vertex

Proof. Let \(C(v)\) be the cost of the tour produced by the fixed-rule run from vertex \(v\), and let \(M=\min_{v\in V} C(v)\). By the definition of a minimum, \(M\le C(v)\) for every \(v\in V\); this proves the first statement. Every fixed-rule run uses tie-breaking choices that are permitted when all tie outcomes are explored. Therefore each fixed-rule tour belongs to the expanded candidate set. The minimum over a set cannot exceed the minimum over a subset, which proves the second statement. This compares the runs performed; it does not compare their minimum with the cost of an optimal TSP tour. \(\square\)

The proposition explains exactly what restarting accomplishes: the cheapest result from the runs cannot be worse than any individual result in those runs. It does not say that restarting finds the best possible Hamiltonian cycle. The set of tours found by nearest neighbor may omit tours that do not follow its local-choice rule.

Common Pitfall: Forgetting the Return Edge

Nearest neighbor makes its greedy choices before the final return, but the return edge is still part of the tour. In the first worked example, the run from \(B\) visits \(B,A,C,D\). Adding only the three selection costs gives \(1+3+3=7\), but \(7\) is the cost of the open route \(B,A,C,D\), not of a tour. The required return \(DB\) costs \(6\), so the completed tour costs \(7+6=13\). Comparing incomplete route costs can therefore select the wrong starting vertex.

A second distinction is equally important: the best tour found is not automatically an optimal tour. The restarting procedure compares a defined collection of nearest-neighbor outputs. It gives no certificate that every possible tour has been considered. Any optimality claim would need an additional argument beyond the fact that one candidate is cheapest among the runs.