Science & Technology

# The Traveling Salesman Problem Has Been Unsolved for Nearly 200 Years

If you've ever been on a cross-country road trip, the traveling salesman problem should feel familiar: If you have a given number of cities, what's the most efficient route you can take to visit each city and land back where you started? It may sound like an easy problem to solve, but it's enough of a challenge that mathematicians and computer scientists have been racking their brains over it for centuries.

## Simple Problem, Impossible Solution

It seems easy enough, especially if you're working with a computer: Just check the distance of every round-trip route possible, and the shortest one is your answer. But think about it: If you're only dealing with, say, five cities, that's 12 round trips to check. But the number of routes begins skyrocketing the more cities you add. A trip between 10 cities has more than 180,000 routes; 15 has more than 43 billion. With enough cities, the number of routes to check could easily overwork the most powerful computers. That way of solving the problem is known as the naive solution, for perhaps obvious reasons.

Throughout the years, great minds have come up with novel ways to solve the problem. In the early days of computer science, people figured out solutions to scenarios involving a specific number of cities, but a way to solve every traveling salesman problem with a single algorithm (that is, a single list of rules a computer can follow to find the solution) remains elusive. In the 1970s, mathematician Richard Karp published a paper that suggested we might never find the solution. He showed that the problem is "NP-hard," which means that there will never be an algorithm to solve it.

## Inching Ever Closer

That doesn't mean computer science is ready to give up on the traveling salesman problem. In 1976, English mathematician Nicos Chrisofides developed an algorithm that can find routes guaranteed to be at most 50 percent longer than the real shortest route. According to Quanta magazine, "Christofides' algorithm starts by looking not for the shortest round-trip route, but the shortest 'spanning tree' — a collection of branches linking the cities, with no closed loops. Unlike the shortest round-trip route, the shortest spanning tree is easy to construct efficiently: Start by finding the shortest highway connecting two cities; that's the first branch. To add the next branch, find the shortest highway connecting a new city to one of those two — and so on until all the cities have been reached." This tree doesn't create a round-trip route, so it's not a real solution, but with some small alterations, it gets surprisingly close to solving the problem. Since then, other mathematicians have built upon Christofides' method to get even closer to the answer.

Other experts have tried getting to the bottom of it using "fractional" techniques — that is, calculating the answer to a small portion of the problem and using that to approximate the answer to the whole problem. In 2010, Amin Saberi, Shayan Gharan, and Mohit Singh developed a new algorithm that beat Christofide's by a hair. In 2012, András Sebo and Jens Vygen got the closest yet with a solution that's at most 40 percent longer than the perfect solution, which is a sizeable improvement over Christofide's 50 percent. Rest assured, that's not the end. This nearly two-century-old problem still has plenty of mystery for experts to uncover.

For more mathematical puzzlers, check out the national bestseller "Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem" by Simon Singh. We handpick reading recommendations we think you may like. If you choose to make a purchase, Curiosity will get a share of the sale.

Ashley Hamer