Chapter seventeen

The traveling salesman has feelings too.

In the late 1950s, a small group of mathematicians at the RAND Corporation began working on a problem that, on its surface, looked almost trivially simple.

The problem was this. Imagine a salesman who has to visit a number of cities, exactly once each, and return home. The distances between every pair of cities are known. What is the shortest possible route?

This is, on first encounter, the kind of problem a moderately bright twelve-year-old would assume could be solved by writing down a few rules and following them carefully. The twelve-year-old would be wrong. The problem turns out to be one of the hardest problems in mathematics, and the reason it is hard is one of the most important discoveries about the structure of computation that humans have ever made.

I want you to register, before this chapter begins, that what I am about to describe is not a parable. It is not a metaphor. It is a precise, well-defined, technically real piece of mathematics, with consequences that have shaped the entire computer science of the last sixty years. The application to anxious life, which we will reach by the middle of the chapter, is, I will argue, exact. The anxious mind is, on most evenings, trying to solve a traveling salesman problem in its head, and the failure to solve it is not a moral failure. It is a complexity-theoretic one.

Let me describe why the problem is hard, because the badness is more specific than just "lots of routes."

If there are five cities, there are roughly twelve possible routes to consider, after accounting for symmetry. Twelve is a number a computer, or even a careful human, can handle in a few seconds. Find them all. Compare them. Pick the shortest.

If there are ten cities, there are about a hundred and eighty thousand routes. Still tractable. A modest computer dispatches this in a fraction of a second.

If there are twenty cities, there are about six hundred quintillion routes. A modern computer working at top speed would, in principle, take longer than the age of the universe to enumerate all of them.

The number of routes grows, technically, as n!, the factorial of the number of cities. The factorial function is one of the most violently expanding functions in mathematics. It does not double when you add a city. It multiplies by the number of cities. Going from twenty cities to twenty-one cities multiplies the number of routes by twenty-one. Going from a hundred to a hundred and one multiplies by a hundred and one. The problem, in this sense, becomes intractable not gradually but with what amounts to violent suddenness, somewhere between fifteen and twenty cities for a computer running at the limits of what is currently possible.

This kind of behavior, where the number of possibilities grows so fast that no machine of any plausible size can enumerate them, is called combinatorial explosion. The traveling salesman problem is the canonical example, but it is not the only one. A large family of problems, called NP-hard problems, exhibit this property. They are problems for which no efficient algorithm is known, and for which most theoretical computer scientists believe no efficient algorithm can possibly exist.

The wall in Figure 17.1 is not a feature of current technology. The wall is, in the most precise mathematical sense, a feature of the problem. No amount of additional computational power, no quantum computer of any plausible scale, no faster processor, no smarter implementation, will move the wall to the right by more than a small amount. The wall is, on inspection, the shape of the problem itself.

This is, when you first encounter it as a working programmer, an extraordinary discovery. The world contains problems that, in a precise technical sense, cannot be solved by any feasible amount of brute force. The fact is true regardless of how clever you are. The fact is true regardless of how hard you try. The fact is, in the language of the field, fundamental.

Now I want to apply this to the anxious mind, because the application is more precise than people who have not been there assume.

The anxious mind, on a typical evening, runs a process that goes something like the following. What is the optimal allocation of my time over the next year? Given my work, my health, my relationships, my finances, my creative projects, my obligations, my unspoken needs, and my undeclared ambitions, what is the right way to arrange the available hours so that I am, by the end of the year, where I most want to be?

This is, on inspection, not a metaphor. This is, in technical terms, an instance of a combinatorial optimization problem with on the order of dozens of variables, hundreds of constraints, and an objective function that the mind itself cannot quite specify. The mind treats the problem as if it were tractable. The mind runs the problem through, plans, replans, lies awake at three in the morning revising the schedule for the third time, and never arrives at the optimal solution. The failure to arrive is not a sign of insufficient cleverness. The failure to arrive is a sign that the mind is attempting an NP-hard computation in wetware that, by design, was not built for it.

The same is true of many smaller decisions. Who should I invite to this dinner so that everyone gets along? NP-hard. The problem of seating people who get along, on a small graph of pairwise compatibilities, is a known combinatorial optimization problem, and the exact solution scales badly. What is the best order in which to do these eleven small tasks before the deadline? NP-hard, in general. What is the right configuration of friendships, partners, and family members for me to have in my life? So far outside the reach of any known algorithm that even framing the question is, technically, suspect.

I want to say plainly what the anxious mind has been doing wrong, because saying it plainly is the beginning of letting it go. The anxious mind has been treating intractable problems as tractable ones. The anxious mind has been running, every night, an optimization that has no efficient solution, on a machine that has no spare cycles, with an objective function it cannot quite name, and has been concluding, when the optimization fails to terminate, that the failure is a fact about the mind rather than a fact about the problem.

The fact about the problem is that it is NP-hard. No amount of additional thinking will make it tractable. The mind, asked to solve such a problem exactly, has approximately the same chance of success as a five-dollar laptop asked to enumerate all routes through a thousand cities. The chance is, in the technical sense, indistinguishable from zero.

Now the good news, because computer science has, over the last sixty years, spent enormous effort developing tools for living with NP-hard problems.

The tools are called heuristics and approximation algorithms. The names sound technical. The ideas behind them are, on inspection, the ideas behind every piece of practical wisdom anyone has ever offered about how to live well.

A heuristic is a rule that produces a good-enough answer, quickly, without any guarantee that the answer is optimal. The most famous heuristic for the traveling salesman problem is called nearest neighbor. It says: at every city, go to the closest unvisited city next. This is, in computer science terms, the greedy algorithm we met in Chapter 12, and it has the same property here as it did there: it is fast, it is simple, it is often wrong, and on average it produces a route that is about twenty-five percent longer than the optimal one.

Twenty-five percent worse than optimal sounds bad, until you realize that the alternative is not finding the optimal route. The alternative is not finishing the computation in any human lifetime. A heuristic that is twenty-five percent worse than optimal but finishes in a millisecond is, in the relevant practical sense, infinitely better than an exact algorithm that finishes in a million years. The heuristic is not a worse solution to the same problem. The heuristic is the only available solution to the actual problem, which is find an answer in time to use it.

There are better heuristics. There are heuristics that produce routes within a few percent of optimal, on most inputs, for problems with thousands of cities. There are clever combinations of heuristics that, over decades of research, have become extraordinarily good at producing very good answers very fast. The whole field of operations research is, in some real sense, the disciplined study of how to find good-enough answers to problems for which optimal answers cannot, in principle, be found.

The grown-up response to an NP-hard problem is not to find the optimal solution. The grown-up response is to choose a heuristic, run it, take the answer it gives you, and live inside the answer. The answer is not optimal. The answer is also, almost certainly, good enough. The remaining gap between the heuristic and the unattainable optimum is the price you pay for finishing the computation in time to use the result, and the price is, in almost every case, worth paying.

Here, briefly, is what this looks like in code, on a tiny version of the traveling salesman problem with eight cities.

import itertools
import math
import random
import time


def distance(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])


def tour_length(cities, route):
    total = 0
    for i in range(len(route)):
        total += distance(cities[route[i]], cities[route[(i + 1) % len(route)]])
    return total


def exact_tsp(cities):
    """
    Try every permutation. Returns the shortest route.
    Tractable only for small n (say, < 12).
    """
    n = len(cities)
    best_route = None
    best_length = float('inf')
    # Fix the starting city to avoid counting rotations
    for perm in itertools.permutations(range(1, n)):
        route = (0,) + perm
        L = tour_length(cities, route)
        if L < best_length:
            best_length = L
            best_route = route
    return best_route, best_length


def nearest_neighbor_tsp(cities, start=0):
    """
    Greedy heuristic: from the current city, always go to
    the nearest unvisited city.
    """
    n = len(cities)
    unvisited = set(range(n))
    route = [start]
    unvisited.remove(start)
    current = start
    while unvisited:
        nxt = min(unvisited, key=lambda c: distance(cities[current], cities[c]))
        route.append(nxt)
        unvisited.remove(nxt)
        current = nxt
    return tuple(route), tour_length(cities, route)


# Set up eight random cities
random.seed(42)
cities = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(8)]

# Time the exact algorithm
t0 = time.time()
exact_route, exact_length = exact_tsp(cities)
t_exact = time.time() - t0

# Time the heuristic
t0 = time.time()
heur_route, heur_length = nearest_neighbor_tsp(cities)
t_heur = time.time() - t0

print(f"Exact:     length {exact_length:.1f}, took {t_exact:.4f}s")
print(f"Heuristic: length {heur_length:.1f}, took {t_heur:.6f}s")
print(f"Gap:       {(heur_length - exact_length) / exact_length * 100:.1f}% worse than optimal")

On my machine, with eight cities, the exact algorithm takes a few hundredths of a second and finds the truly optimal tour. The heuristic takes about a hundred microseconds and finds a tour that is, on this particular set of cities, somewhere between five and twenty percent longer than the optimal one, depending on the random seed.

The exact algorithm at eight cities is fine. At fifteen cities, it begins to be slow. At twenty-five cities, it would not finish before you got bored. At fifty cities, it would not finish in any number of human lifetimes. The heuristic, at all of these sizes, finishes in a fraction of a second and produces a route that is, in practical terms, perfectly usable.

This is the situation. This is also the model. The optimal life is, in technical terms, like the exact traveling salesman tour: it exists, mathematically, in the space of possible lives, but no available computation can find it before you have run out of time to live it. The heuristic life is the one you can actually have. It is, by construction, somewhat worse than optimal. It is also, by construction, the only one that finishes computation in time to be lived.

I want to close Part two with a quiet observation, because Chapter 17 is the last chapter of Part two and the chapter should mark the closing.

Part two has been the toolkit. Fourteen chapters of mathematics, applied carefully to specific features of the anxious mind. Each chapter has named a particular bug and offered a particular fix. The bugs are different. The fixes are different. But there is, on inspection, a single underlying observation that has run through almost all of them, and I want to name it now, before Part three begins.

The observation is that almost every feature of anxious cognition we have examined turns out, on close inspection, to be a misapplication of a faculty that is otherwise useful. The brain's threat detection is a useful faculty that has been miscalibrated. The brain's recursion is a useful faculty that has lost its base case. The brain's optimization is a useful faculty that has been pointed at the wrong objective. The brain's self-observation is a useful faculty that has been run at a frequency the system cannot absorb. The brain's combinatorial reasoning is a useful faculty that has been applied to problems too large for it to solve.

The brain, in almost every chapter, has not been malfunctioning. The brain has been doing exactly what it was designed to do, on inputs it was not designed for. The fix, in almost every chapter, has not been to repair the brain. The fix has been to recognize the mismatch between the brain's faculty and the world's actual structure, and to adjust the application accordingly. Take a heuristic instead of an optimum. Install a base case. Reduce the measurement frequency. Read both the function and the derivative. Compute a Bayesian update on better-conditioned evidence.

None of this is, in the strict sense, repair. All of this is, in the strict sense, recalibration.

Part three takes the next step, which is to ask: now that we have spent fourteen chapters recalibrating the existing faculties, can we go further? Can we write new code? Can we, deliberately, add habits and patterns that the original installation did not include? Can we, in other words, take the kernel we have spent Part two patching, and begin to extend it?

The answer, as the next four chapters will argue, is yes. With caution. With patience. With humility about the limits of self-modification. But yes.

End of Part two The toolkit is now complete. The bugs have been diagnosed and the recalibrations described. Part three takes the next step.