How a TSP Solver Decides What to Try Next

A TSP solver is always making little bets.

Not the final bet; not “this is the optimal tour.” Much smaller ones. Try swapping these two cities. Try mutating this edge. Try looking near this part of the route, not that part. Try a move drawn from a biased distribution, not a uniform one.

That is what I find interesting about the sampling.h file from my TSP project: it makes those bets explicit. Instead of treating randomness as a black box, it breaks the search machinery into several small samplers, each doing a slightly different job.

Sampling inside a combinatorial optimizer is not decoration. It is a set of search operators.

The conceptual shift

Earlier in the series, sampling meant things like: choose a representative subset, choose an item with the right probability, estimate something from less data. Inside a TSP metaheuristic, sampling means something else:

Choose what to try next.

That is much closer to the exploration/exploitation language from metaheuristics. Exploration asks for diversity in proposed moves. Exploitation asks for pressure toward more promising regions of the search space.

The cleanest primitive: pick distinct indices

The sample_indexes(low, high, k, random) function samples k distinct indices from a range, using Robert Floyd’s algorithm.

That is a good primitive for a search operator. If your neighborhood move needs a few distinct positions in a tour, this is the right tool. It solves exactly the problem you have without wasting time proposing duplicates.

This is the point where without-replacement sampling stops being a probability exercise and starts becoming an optimization tool.

From indices to moves

Right below that, sample_pair(low, high, random) samples two distinct indices and optionally sorts them before returning the pair.

A small function, but it captures a big idea: a search move often begins as a sampled pair. In TSP, a pair can mean two cities to swap, two cut points for a segment move, or two edges that define a neighborhood operation.

The sampler decides which local part of the solution becomes editable.

Sometimes you want constraints, not just randomness

The most metaheuristic-flavored function is sample_constrained_window. It samples two uniform random numbers, sorts them, converts them into positions, forces the second one to be at least delta_min away from the first, and clips it to be at most delta_max away.

That is what good randomness looks like in optimization: not fully free, not fully deterministic, but shaped by the geometry of the move you care about.

Uniform randomness is often too naive. If a search operator only makes sense when two positions are neither too close nor too far apart, the proposal distribution should reflect that. This is the kind of rule that uses randomness, but still respects the geometry of the move.

function sampleConstrainedPair(
  low: number,
  high: number,
  deltaMin: number,
  deltaMax: number
): [number, number] {
  const space = high - low - deltaMin;

  let u1 = Math.random();
  let u2 = Math.random();
  if (u1 > u2) [u1, u2] = [u2, u1];

  const a1 = low + Math.floor(u1 * space);
  let a2 = low + Math.floor(u2 * space) + deltaMin;

  if (a2 > a1 + deltaMax) a2 = a1 + deltaMax;
  return [a1, a2];
}

Weighted choice shows up too

The file also has sample_from_probabilities, which uses a discrete distribution over supplied weights and maps sampled indices back into data values.

That is ordinary weighted sampling with replacement. It matters because not every move deserves equal attention. Once your algorithm has scores, penalties, or heuristics attached to candidate moves, weighted sampling becomes a natural way to bias search without collapsing into determinism.

The same conceptual move from earlier in the series: turn scores into structured randomness. Only now the objects are not labels or rows. They are candidate search moves.

Weighted sampling without replacement

Then there is weighted_sample_indexes. It assigns each candidate a random key of the form

where $r_i$ is uniform random noise and $p_i$ is the weight, and then keeps the best k candidates via a priority queue.

The pattern is useful because sometimes the right way to sample a weighted subset is not to keep redrawing items. It is to assign each candidate a random key and rank by that key.

This is an instance of the Efraimidis-Spirakis technique. It feels closer to search than to textbook probability.

See also: Stochastic Greedy for Submodular Maximization

There is a sibling idea on this site that belongs naturally next to this case study: stochastic greedy for submodular maximization. That post makes the random-subsampling pattern explicit. Instead of scanning all remaining elements, it samples a random subset $Q$, picks the best inside $Q$, and repeats.

The shared pattern is to use a small random view of a large search space to make each step much cheaper, then let repetition recover the larger behavior.

In this TSP post, randomness samples moves or neighborhoods. In the submodular post, randomness samples a candidate subset of elements. That is exactly the analogy that makes these TSP samplers feel like part of a broader software pattern rather than a TSP-specific curiosity.

The bigger pattern

A classifier samples a label. A language model samples a token. A TSP solver samples a move. Different object, same deeper pattern:

Sampling is controlled choice under uncertainty.

The next post changes the object again: instead of search moves, we go back to machine learning and ask how a model turns raw scores into something probabilistic enough to sample from. That is the next post.