The Travelling Salesman Problem

In the knapsack, the oracle scanned 64 subsets of six items, and that scan was cheap. The candidate-solution count was an exponential function of the item count, but the base of the exponent was two, and for six items 64 stayed a small number. In the travelling salesman problem, the candidate count is not subsets but orderings, and that number grows far faster.

The problem is this: cities and the distances between them are given, and the shortest closed tour that visits every city exactly once and returns to the start is sought. This lesson answers two questions separately. The first is measurable: how far, in percent, does an approximate solution deviate from the oracle. The second is not answered in this course: why this problem is hard. The second question is a classification question and belongs to the Theory of Computation course; here only the question itself is set up.

• CP10. City positions come from the shared definition’s generator: a random point on a 30-by-30 grid. Seed 20260218, second pool 20260219.
• CP11. Each pool has 20 samples, 8 cities per sample. The city count is kept small so the oracle can be run; large city counts are conveyed by counting.
• CP12. Distance is an integer: the integer square root of the sum of the squared coordinate differences. Floating-point numbers are not used, so equality between two tours can be tested exactly.
• CP13. The oracle is exhaustive enumeration: city zero is fixed, and every ordering of the remaining seven cities is tried; since a tour’s reverse is the same tour, half are eliminated, leaving 2520 tours.
• CP14. The measure is steps. A step is computing the length of one edge.
• CP15. Deviation is written as a percentage: the pattern’s tour minus the best tour, divided by the best tour. Worst-case deviation is placed alongside the average; the average alone is misleading.
• CP16. The two-opt improvement removes two edges from the tour and reconnects it by reversing the segment between them. It continues until no improvement remains.
• CP17. Large city counts are not run, they are counted. The exhaustive-enumeration table is produced by computing factorials; no tour is actually scanned.
• CP18. The name of the difficulty is not written in this lesson. Complexity classes, reductions, and approximation ratios belong to Theory of Computation.
• CP19. How deviation changes with city count is also swept. A separate pool is generated for each city count; the rows are not extensions of one another.

The Oracle and Two Approximate Solutions

The nearest-neighbor procedure follows intuition directly: from the current city, go to the nearest unvisited city, and return to the start once done. Two-opt takes the resulting tour and fixes it locally; if two edges in the tour cross, removing them and reversing the segment between them shortens the tour.

Neither is claimed to be correct. The oracle finds the best tour on every sample by exhaustive enumeration, and both patterns are measured against it.

from itertools import permutations
from math import isqrt

SEED = 20260218


def generator(seed):
    d = seed

    def next_val(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_val


def cities(seed=SEED, samples=20, n=8):
    """The shared definition's generator; each sample is n cities' (x, y) positions."""
    r = generator(seed)
    return [[(r(30), r(30)) for _ in range(n)] for _ in range(samples)]


def distance(p, q):
    return isqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def oracle_exhaustive(k, c):
    """City zero is fixed; every ordering of the remaining cities is tried."""
    best = None
    for p in permutations(range(1, len(k))):
        if p[0] > p[-1]:
            continue
        tour, previous = 0, 0
        for i in p:
            c.count()
            tour += distance(k[previous], k[i])
            previous = i
        tour += distance(k[previous], k[0])
        if best is None or tour < best:
            best = tour
    return best


def nearest_neighbor(k, c):
    remaining, path, current, tour = set(range(1, len(k))), [0], 0, 0
    while remaining:
        best_i, best_d = None, None
        for i in remaining:
            c.count()
            d = distance(k[current], k[i])
            if best_d is None or d < best_d:
                best_i, best_d = i, d
        remaining.remove(best_i)
        path.append(best_i)
        tour, current = tour + best_d, best_i
    return tour + distance(k[current], k[0]), path


def two_opt(k, path, c):
    n = len(path)
    tour = sum(distance(k[path[i]], k[path[(i + 1) % n]]) for i in range(n))
    improved = True
    while improved:
        improved = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                c.count()
                a, b, cc, d = path[i - 1], path[i], path[j], path[(j + 1) % n]
                delta = (distance(k[a], k[cc]) + distance(k[b], k[d])
                         - distance(k[a], k[b]) - distance(k[cc], k[d]))
                if delta < 0:
                    path[i:j + 1] = reversed(path[i:j + 1])
                    tour, improved = tour + delta, True
    return tour


for seed in (20260218, 20260219):
    ha, totals = 0, {"nearest neighbor": [0, 0, 0.0, 0.0], "two-opt         ": [0, 0, 0.0, 0.0]}
    for k in cities(seed):
        sh = Counter()
        best = oracle_exhaustive(k, sh)
        ha += sh.steps
        s1, s2 = Counter(), Counter()
        t1, path = nearest_neighbor(k, s1)
        t2 = two_opt(k, list(path), s2)
        for name, t, s in (("nearest neighbor", t1, s1), ("two-opt         ", t2, s2)):
            r = totals[name]
            r[0] += 0 if t == best else 1
            r[1] += s.steps
            dev = 100.0 * (t - best) / best
            r[2], r[3] = r[2] + dev, max(r[3], dev)
    print("seed", seed, "| oracle steps", ha)
    for name, r in totals.items():
        print(f"  {name} split {r[0]:2d}/20 | pattern steps {r[1]:4d}"
              f" | avg deviation percent {round(r[2] / 20, 2)}"
              f" | worst percent {round(r[3], 2)}")

seed 20260218 | oracle steps 352800
  nearest neighbor split 17/20 | pattern steps  560 | avg deviation percent 9.3 | worst percent 33.33
  two-opt          split  2/20 | pattern steps  819 | avg deviation percent 0.49 | worst percent 7.59
seed 20260219 | oracle steps 352800
  nearest neighbor split 18/20 | pattern steps  560 | avg deviation percent 10.65 | worst percent 26.67
  two-opt          split  6/20 | pattern steps  924 | avg deviation percent 1.13 | worst percent 6.59

Reading the Deviation

Three numbers side by side: the oracle at 352,800 steps, nearest neighbor at 560 steps, 17 split samples. The pattern spends 630 times fewer steps and fails to find the best tour on 17 of 20 samples. But the split-sample count alone is not enough here, because the question is not “is it correct” but “how far off”. Average deviation is 9.3 percent and worst-case deviation is 33.33 percent. Writing the average alone would hide the existence of a tour a third longer than optimal.

Two-opt takes the same tour and applies local fixes. The split count drops from 17 to 2, average deviation from 9.3 percent to 0.49 percent, worst-case deviation from 33.33 percent to 7.59 percent. The cost of this is 819 steps instead of 560, that is, 46 percent more work. The procedure is still not the oracle: it fails to find the best tour on two samples, and it cannot know that it has failed.

The second pool is mandatory. With seed 20260219, nearest neighbor splits on 18 samples, average deviation 10.65 percent; two-opt splits on 6 samples, average deviation 1.13 percent. Nearest neighbor’s result is the same on both pools: it misses the best tour on almost every sample. Two-opt’s split count rises from 2 to 6, and this difference is above the resolution; that is, how many samples two-opt finds the best tour on depends on the pool and cannot be generalized from a single one. The order of magnitude of the average deviation, however, does not change: it stays around one percent.

Where the Oracle Runs Out

The oracle spending 352,800 steps on eight cities is not the problem. The problem is how this number grows with city count. The tour count is half of every ordering of the remaining cities once city zero is fixed. This number is shown not by running it but by counting.

from math import factorial


def group(x):
    return f"{x:,}".replace(",", ".")


print(" n | tours | oracle steps | nearest neighbor steps | ratio")
for n in (8, 10, 12, 14, 16, 18):
    tours = factorial(n - 1) // 2
    oracle = tours * (n - 1)
    pattern = n * (n - 1) // 2
    print(f"{n:2d} | {group(tours):>22s} | {group(oracle):>25s} |"
          f" {pattern:4d} | {group(oracle // pattern)}")

 n | tours | oracle steps | nearest neighbor steps | ratio
 8 |                  2.520 |                    17.640 |   28 | 630
10 |                181.440 |                 1.632.960 |   45 | 36.288
12 |             19.958.400 |               219.542.400 |   66 | 3.326.400
14 |          3.113.510.400 |            40.475.635.200 |   91 | 444.787.200
16 |        653.837.184.000 |         9.807.557.760.000 |  120 | 81.729.648.000
18 |    177.843.714.048.000 |     3.023.343.138.816.000 |  153 | 19.760.412.672.000

Going from eight cities to eighteen, the oracle’s steps rise from 17,640 to 3,023,343,138,816,000; nearest neighbor’s steps rise from 28 to 153. The ratio climbs from 630 to over nineteen trillion. This table is not a speed claim; it is a count of where the oracle becomes impossible to run.

The conclusion that follows is the harshest form of the course’s third claim. Brute force is an oracle, but it cannot be an oracle at every scale. The 9.3 percent deviation measured at eight cities cannot be measured at eighteen, because the best tour to compare against is unknown. Every sentence written about an approximate solution’s quality on large inputs either generalizes from a deviation measured on small input or uses a lower bound. Neither is proof, and this lesson does not present either as proof.

What Deviation Does With City Count

The previous section’s last sentence leaves a question: what does a deviation measured on small input say about large input. This question cannot be fully answered, but which direction the deviation moves in the range where the oracle can still be run can be measured. City count is swept from five to nine.

from itertools import permutations
from math import isqrt

SEED = 20260218


def generator(seed):
    d = seed

    def next_val(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_val


def cities(seed=SEED, samples=20, n=8):
    r = generator(seed)
    return [[(r(30), r(30)) for _ in range(n)] for _ in range(samples)]


def distance(p, q):
    return isqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)


def oracle_exhaustive(k):
    best = None
    for p in permutations(range(1, len(k))):
        if p[0] > p[-1]:
            continue
        tour, previous = 0, 0
        for i in p:
            tour += distance(k[previous], k[i])
            previous = i
        tour += distance(k[previous], k[0])
        if best is None or tour < best:
            best = tour
    return best


def nearest_neighbor(k):
    remaining, current, tour = set(range(1, len(k))), 0, 0
    while remaining:
        best_i = min(remaining, key=lambda i: distance(k[current], k[i]))
        tour += distance(k[current], k[best_i])
        remaining.remove(best_i)
        current = best_i
    return tour + distance(k[current], k[0])


print(" n | split / 20 | avg deviation | worst deviation")
for n in (5, 6, 7, 8, 9):
    split, total, worst = 0, 0.0, 0.0
    for k in cities(n=n):
        e, t = oracle_exhaustive(k), nearest_neighbor(k)
        if t != e:
            split += 1
        dev = 100.0 * (t - e) / e
        total, worst = total + dev, max(worst, dev)
    print(f"{n:2d} | {split:11d}  | percent {round(total / 20, 2):5} "
          f"   | percent {round(worst, 2)}")

 n | split / 20 | avg deviation | worst deviation
 5 |          12  | percent  5.03    | percent 16.67
 6 |          14  | percent  6.29    | percent 17.57
 7 |          15  | percent  7.17    | percent 17.86
 8 |          17  | percent   9.3    | percent 33.33
 9 |          14  | percent  9.77    | percent 22.99

Average deviation is 5.03 percent at five cities, 9.77 percent at nine. It rises in all five rows and roughly doubles. The split-sample count, however, is not regular: 12, 14, 15, 17, then 14. This irregularity is expected, because each row is a separate pool generated for its own city count; the nine-city samples are not extensions of the eight-city samples.

The only thing that can be drawn from the table is the direction itself: deviation rises with city count. This suggests that the 9.3 percent measured at eight cities is an underestimate for large inputs. It suggests — it does not prove. Saying something about eighteen cities from five data points spanning five to nine means stepping outside a measured range, and this lesson does not take that step.

Where the Question of Why It Is Hard Belongs

Everything measured so far is concrete: steps, deviation, split samples. One thing remains unmeasured. Is there a procedure fundamentally cheaper than exhaustive enumeration, or is there a difficulty inherent to this problem’s nature.

This question is not answered in this course, and no attempt is made to answer it. Answering it requires classifying problems by degree of difficulty, transforming one problem into another, and establishing proven bounds on how far an approximate solution can deviate from the best. All of these tools belong to the Theory of Computation course. All that is done here is to separate the question from its measurable part: deviation is measured, the name of the difficulty is not.

This distinction has a practical consequence. Knowing that a problem is hard does not substitute for knowing an approximate solution’s deviation. Saying “it is already a hard problem” without measuring the deviation leaves the pattern without an oracle.

Summary

• In the travelling salesman problem, the candidate-solution count is not subsets but orderings; 2520 tours at eight cities, 177,843,714,048,000 at eighteen.
• The oracle spends 352,800 steps on 20 samples; nearest neighbor finishes in 560 steps but misses the best tour on 17 of 20 samples.
• Deviation averages 9.3 percent, worst case 33.33 percent; writing the average alone hides the worst case.
• Two-opt brings the split count down to 2 and average deviation down to 0.49 percent, at a cost of 819 steps instead of 560; since the split count rises to 6 on the second pool, this number depends on the pool.
• The oracle cannot be run at every scale; there is no deviation measured on large input, only a generalization made from small input.
• The question of why the problem is hard belongs to the Theory of Computation course and is not answered here.

Next Step

In the travelling salesman problem, the oracle was exhaustive enumeration and the pattern was an approximate tour. The next lesson takes up a more unsettling situation: one where the pattern is a proven procedure, but the problem it is applied to changes. Shortest-path algorithms were proven in the Algorithms course; when the same procedure is turned toward the longest path, on how many graphs does it give a wrong answer, and which assumption falling away is the source of that wrongness.