Lecture 21: Tuning a TSP Algorithm

What this lecture covers

Guest lecturer Jon Bentley walks through a single case study in performance engineering: solving the traveling salesperson problem (TSP) by brute force and then speeding it up step by step. He starts from a plain recursive permutation search and, through a sequence of small, well-motivated changes, turns an algorithm that can barely handle 13 cities into one that solves a 52-city instance overnight. The lecture sits near the end of the course as a synthesis exercise, pulling together recursion, data structures, caching, and search pruning that earlier lectures covered separately.

After watching, you should be able to write a recursive routine that enumerates permutations or subsets of a set, recognize when a search can be pruned with a lower bound, and see how caching and better starting heuristics compound to produce order-of-magnitude speedups without changing the algorithm's asymptotic class.

Key ideas

• Recursive enumeration: generating all 2^n subsets or n! permutations of a set is naturally expressed as a recursive function that fixes one element and recurses on the rest.
• Traveling salesperson problem (TSP): given a set of cities, find the shortest tour that visits every city once; it is NP-hard, so exact search is inherently expensive.
• Fixing the starting city: since a tour can begin anywhere, fixing one city up front removes a factor of n from the search without changing the answer.
• Branch-and-bound pruning: if the distance traveled so far plus a lower bound on the remaining distance already exceeds the best tour found, the search can abandon that branch.
• Minimum spanning tree (MST) as a lower bound: the cost of an MST on the unvisited cities is always less than or equal to the cost of completing the tour, so it makes a cheap, effective bound.
• Caching: because the same MST subproblems recur during search, storing computed MST distances (in a table or hash table) avoids redundant work.
• Greedy starting tour: visiting the nearest unvisited city first, instead of visiting cities in arbitrary order, gives the search a good tour early, which improves pruning.
• Compiler optimization and hardware: turning on -O3 and running on modern hardware produced larger speedups (factors of 25 and 150 respectively) than many algorithmic tweaks, a reminder to measure rather than assume.

Walkthrough

Recursive generation warm-up (3:05)

Before touching the TSP, Bentley shows how to enumerate all subsets of a set recursively: fix the last element to 0, recursively generate all subsets of the rest, then fix it to 1 and recurse again. The point is that this simple recursive pattern generalizes cleanly to permutations, which is what the rest of the lecture needs.

Introducing the traveling salesperson problem (7:14)

Bentley frames the TSP with the historical example of Abraham Lincoln's judicial circuit riders choosing an efficient route between towns, then generalizes it to any weighted graph. He gives further real examples (plotting red and blue precinct dots, drilling circuit boards, sequencing cars on an assembly line) to show the problem shows up whenever reordering work reduces total movement cost, and notes the TSP is NP-hard and one of the first problems proven to be so.

A brute-force C program (15:21)

The first working version recursively generates all n! permutations of the cities, computes each tour's total distance, and keeps the best one. Bentley shows that runtime grows by roughly a factor of n each time n increases by one, so times for n=14 and beyond quickly become hours, weeks, and months of CPU time — motivating the need for something smarter than brute force.

Cheap constant-factor wins (23:34)

Before changing the algorithm, Bentley measures what compiler optimization (-O3) and 20 years of hardware improvement are worth: a factor of about 25 from optimization flags and about 150 from newer machines. He then shows algorithmic constant-factor cuts: fixing the starting city (factor of n) and carrying the running sum along recursive calls instead of recomputing it each time (a further constant factor).

Pruning with a minimum spanning tree bound (50:03)

The first big structural change is to stop extending a partial tour as soon as its distance so far is already worse than the best tour found. Bentley then strengthens the bound by adding the cost of a minimum spanning tree over the remaining cities, computed with the Prim-Dijkstra method, using a bitmask to represent the remaining city set. This drops runtime for a 17-city problem from many seconds to a fraction of a second.

Caching MST computations and starting greedy (59:14)

Profiling shows most remaining time goes into recomputing minimum spanning trees, so Bentley caches MST distances in a table indexed by the bitmask, then in a hash table for larger problems, since the same subsets recur across branches. He then replaces the arbitrary visiting order with a greedy nearest-neighbor order (using a small insertion sort), which produces a better starting tour and further improves how much the bound can prune.

How far the combined techniques reach (1:05:17)

Combining all the changes, Bentley narrates pushing the solvable problem size live from 30 cities up to 52 cities over a long overnight run, contrasting this with what would have been possible on 1997 hardware with the same code. He closes by summarizing the toolkit — recursion, pruning, caching, hashing, and greedy heuristics — as broadly applicable performance-engineering techniques, not TSP-specific tricks.

Before you watch

• Be comfortable with recursive functions and basic recursion trees, since the entire talk builds on a recursive permutation generator.
• Know what a minimum spanning tree is and roughly how Prim's or Dijkstra's algorithm builds one; the lecture uses this as a black box.
• Some familiarity with hash tables and bitmask representations of sets will help the later optimizations make sense.

Check your understanding

1. Why does fixing the starting city of the tour reduce the search space by a factor of n without losing any candidate tours?
2. Explain why the cost of a minimum spanning tree on the remaining unvisited cities is always a valid lower bound on the cost to complete the tour.
3. Why does caching minimum spanning tree distances by the bitmask of remaining cities pay off during this search, when it might not in a search where subproblems rarely repeat?
4. How does starting from a greedy nearest-neighbor tour improve the effectiveness of branch-and-bound pruning compared to starting from an arbitrary tour?
5. Bentley finds that turning on compiler optimization flags gives a bigger speedup than several algorithmic changes. What does this suggest about the order in which a performance engineer should look for wins?