Math
Travelling salesman
A tour that shortens while you watch - greedy, 2-opt uncrossing edge by edge, annealing climbing over the wall - against the exact optimum for thirteen cities and brute force over every tour for eight.
What happens
Compare nearest-neighbour construction, 2-opt improvement and simulated annealing on the same cities. A 2-opt local optimum has no improving two-edge exchange; it need not be the globally shortest tour. Annealing sometimes accepts longer tours to escape local minima, without guaranteeing the optimum in a finite run.
The minimum spanning tree is a lower bound on every tour. For these Euclidean distances, doubling a spanning tree and shortcutting repeated visits proves that the optimal tour is at most twice the minimum spanning tree. This bound concerns the optimum and a suitable tree-based construction; it does not constrain every greedy or intermediate tour.
The small exact scene uses Held–Karp dynamic programming over subsets, with O(N²·2^N) time rather than enumerating every permutation. The eight-city scene can enumerate every distinct tour. Exact algorithms need not inspect most permutations, but no polynomial-time exact algorithm is known for the general travelling-salesman problem. Compare the measured heuristic tours with the exact reference where available.
Equations used in the module
Equations
cities: N points in [−1, 1]² from the shared die (seed 3); tour length L = Σ |c_k − c_{k+1}| around the cycle; (N − 1)!/2 distinct tours: 2520 for 8, 2.4·10^8 for 13, 1.0·10^46 for 40
greedy: from city 0, always the nearest unvisited (ties by index); 12.8105 for forty cities
2-opt: edges (a, b) and (c, d) with a before c on the tour; Δ = |ac| + |bd| − |ab| − |cd|; the first pair in scan order with Δ < 0 is uncrossed by reversing the segment b … c; repeat until none: 16 uncrossings, 10.5850 - the wall (a local optimum)
annealing: a random pair (i, j), i < j, j − i ≥ 2; accepted if Δ ≤ 0, else with probability exp(−Δ/T); T₀ = 0.3, T ← 0.9997 T each step, 20 000 steps; seed 6: best 10.4954, 462 accepted, 231 uphill; 2-opt on it: 10.2673
bound: MST ≤ L for every tour (a tour minus an edge is a spanning tree), and the tour of a doubled tree shows L_opt ≤ 2·MST; MST = 8.4480 for the forty (GraphTheory's tree, same die); 10.2673 / 8.4480 = 1.215
Held–Karp: dp[S, k] = shortest path from 0 through the set S ending at k; dp[S + k, k] = min over j in S of dp[S, j] + |jk|; 2^N·N² steps; 13 cities, seed 8: optimum 7.4710, tour 0 7 1 3 12 6 8 10 5 4 11 2 9; 2-opt from 50 random tours (Fisher–Yates on seeds 100 …): 7 reach it, worst 1.0789 ×, mean 1.0678 ×
brute force: every permutation of 1 … N − 1 in lexicographic order, each tour once (first < last); 8 cities, seed 3: 2520 tours, best 5.2175 = Held–Karp, longest 11.9462, mean 9.1055
