What Is the Traveling Salesman Problem and Why Is It Hard?

Say you're a delivery driver with seven stops on your list. You want to visit every one of them and drive home, and you want the shortest possible loop that does it. How do you find that route?

Your first instinct is probably: just try every possible order and keep the shortest one. Computers do arithmetic in nanoseconds, so checking a few thousand routes should be instant.

Try it yourself first, by hand, before we get to why that instinct breaks down.

Even with seven cities, finding the shortest loop by eye takes real work. You probably tried an order, backtracked, swapped two stops, tried again. Now imagine doing that with seventy cities instead of seven. The problem doesn't get harder in a straight line. It explodes.

Just check every possible route, right?

Here's the plan: list every possible order the driver could visit the cities in, measure the total distance for each one, and keep the shortest. This is called brute force, and it always finds the true best answer. There's no trick to it and no risk of getting it wrong.

For three or four cities, brute force is instant. Your laptop checks every order before you finish reading this sentence.

But watch what happens as we add more stops.

Adding one city doesn't add work. It multiplies it.

With 3 cities there are only a couple of meaningfully different loops. Add a 4th city and each of those loops can be cut open and the new city inserted in several places. Add a 5th, and every one of those routes branches again.

This is factorial growth. For $n$ cities, the number of distinct loops is:

We divide by 2 because driving a loop clockwise or counterclockwise covers the same ground. The $(n-1)!$ comes from fixing your starting city and then choosing the order of everyone else. For $n = 7$, that's $6! / 2 = 360$ routes, easy. For $n = 15$, it's over 43 billion. For $n = 20$, it's a number with 17 digits.

Slide up to 20 or 25 cities and look at the time readout. A real delivery company might route hundreds of stops in a single day. Brute force isn't just slow for that. It's finished before the universe is.

This is what "hard" means here. Not hard like a tricky exam question. Hard like no computer, running for the rest of time, could ever check every route once you pass a few dozen cities.

So we cheat: always walk to whatever's closest

If checking everything is off the table, we need a shortcut. The simplest one: stand at your current city, look at every city you haven't visited yet, and walk to the nearest one. Repeat until you've visited everyone, then head home.

This is called the nearest neighbor heuristic. A heuristic is just a rule of thumb: a strategy that's fast and usually reasonable, but comes with no promise of being the best.

Press play and watch it run. Notice it never looks ahead and never reconsiders. It just grabs whatever's closest, every single time. That's exactly why it's fast, computing a full tour for $n$ cities this way takes roughly $n^2$ steps, nowhere close to $n!$.

But watch the final gap against the true optimum. Nearest neighbor can back itself into a corner: it grabs all the easy, close cities early and gets left with one far-away straggler at the end, and that last stretch drags the whole tour up. Fast, but not perfect.

A crossing path is always improvable

Here's a useful fact: if a tour's path crosses itself anywhere, it's not the shortest tour. You can always uncross it and end up with something shorter.

Picture two roads on your route that cross like an X. Instead of driving through the X twice, you could swap which city connects to which, so the paths no longer cross, and the total distance goes down. This move is called 2-opt: pick two edges in the tour, and if reversing the stretch of cities between them shortens the total, do it.

Step through the swaps one at a time. Each swap removes a crossing and the length drops a little. Once there are no more crossings left to fix, the algorithm stops, this is called a local optimum: better than every tour one swap away, but not guaranteed to be the best tour overall.

That gap between "can't improve it with one more swap" and "actually the shortest possible" is where a lot of real-world routing software lives. Delivery companies, chip designers, and airlines all run some version of this idea, because getting close to optimal fast beats waiting for perfect and never getting an answer.

This is what "hard" means to a computer scientist

We've seen two very different kinds of difficulty. Brute force is guaranteed correct but takes $O(n!)$ time, so slow it's unusable past a few dozen cities. Heuristics like nearest neighbor and 2-opt run fast, in roughly $O(n^2)$ time, but give up the guarantee of correctness.

That trade-off isn't an accident of these two particular methods. It's the whole problem. The traveling salesman problem belongs to a class computer scientists call NP-hard. Nobody has ever found an algorithm that solves it exactly in a reasonable amount of time as $n$ grows, and most computer scientists believe no such algorithm exists. Proving otherwise would be one of the biggest results in the history of mathematics, it would mean a huge range of problems we currently consider intractable, from cryptography to scheduling, would suddenly become easy too.

So "hard" here doesn't mean nobody has been clever enough yet. It means the problem itself, as far as anyone can prove, resists shortcuts.

The short version

Checking every possible route always finds the best answer, but the number of routes grows factorially, so brute force is only usable for a handful of cities. Heuristics like nearest neighbor build a decent tour fast but can end up meaningfully worse than optimal. Local search methods like 2-opt take any tour and keep improving it until no small change helps anymore, landing somewhere good but not provably perfect. The traveling salesman problem is NP-hard, which is the mathematical way of saying: there's no known shortcut, and probably never will be.

The next time you watch a delivery app calculate a route in half a second, remember it's not solving your seven-stop loop perfectly either. It's doing what you just did with the sliders above: taking a fast, imperfect shortcut, and getting close enough to matter.

All visualizations are interactive React components running entirely in your browser. The optimal routes shown are computed with real brute-force search over every permutation, not looked up. No libraries beyond React.