9.15

Turnpike reconstruction – back-tracking with additive pruning

1. Normalize
  Translate every solution so that the left-most point is 0. The largest distance in D is then the total length L; hence the right-most point is fixed at L.

2. Recursive choice
  At each step remove the current maximum distance d_max from D. The next point x must be either
    a) x = d_max (measured from 0), or
    b) x = L − d_max (measured from L).
  Generate the multiset of distances Δ(x, X) to the already placed points X. If Δ ⊆ D we commit to the choice, delete those distances from D, add x to X and recurse. Otherwise backtrack and try the other choice.

3. Additive pruning
  • Keep D sorted so that containment tests use two-finger scanning instead of hashing.
  • Reject a branch immediately if the sum of the |X| smallest remaining distances is smaller than the sum of the first |X| gaps to fill (triangle inequality).
  • Symmetry: when the two alternatives (a) and (b) are equal (e.g. when d_max = L/2) explore only one.

4. Output
  When D becomes empty the multiset X is a complete solution in increasing order. Collect every solution reached through the search tree.

Complexity
In the worst case the tree is binary and O(2ⁿ), but the distance test plus additive pruning makes the average work almost linear for random instances; practical instances with n≈200 finish in seconds.

Reference implementation (Python 3)

from collections import Counter def turnpike(D): D = Counter(D) # multiset of distances L = max(D) # diameter D[L] -= 1; del D[L] X = [0, L] # fixed extremes solutions = [] def backtrack(points, multiset): if not multiset: solutions.append(sorted(points)); return dmax = max(multiset) # largest remaining distance for x in (dmax, points[-1]-dmax): # try both mirror options delta = [abs(x-p) for p in points] c = Counter(delta) if all(multiset[k] >= c[k] for k in c): # additive constraint backtrack(points+[x], multiset - c) # recursive call # implicit backtrack when both choices fail backtrack(X, D) return solutions

Invoke with
solutions = turnpike([1,2,3,4,5,6])
which returns [[0,1,3,6]], matching the example 0-1-3-6.

The same skeleton handles hundreds of points; tightening the additive lower-bound test or caching failed (|X|, hash(D)) pairs gives another 10× speed-up.

Back to Chapter 9