--- title: 'The Travelling Salesman Problem' source: 'https://academia.sh/en/courses/advanced-algorithms/travelling-salesman-problem' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # The Travelling Salesman Problem Making the best tour found by exhaustive enumeration on eight cities the oracle, and measuring how far two approximate solutions deviate from it in percent: nearest neighbor splits from the oracle on 17 of 20 samples, with an average deviation of 9.3 percent and a worst case of 33.33 percent; the two-opt improvement brings the split count down to 2 and the average deviation down to 0.49 percent, in 819 steps. The oracle spends 352,800 steps on the same 20 samples. The growth of the search space is shown by counting, not by running it: at eighteen cities the tour count is 177,843,714,048,000. The question of why it is hard is referred to the Theory of Computation course. 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. ```python 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**. ```python 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. ```python 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.