Math

Road Trip! Why Mathematicians Are Vexed By The Traveling Salesman Problem

Excited for the August 21 eclipse? Visit our Eclipse 2017 page to explore the science, history, and myths of the event. The Curiosity team will be viewing the eclipse alongside NASA in Carbondale, Illinois. Follow us on Facebook for live videos, trivia, and interviews on the big day.

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.

Related: Are Math Equations Beautiful? Euler's Identity Makes Mathematicians Swoon

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: 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.

Related: The P Versus NP Problem Is One Of Computer Science's Biggest Unsolved Problems

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.

Related: The Millennium Problems Are Seven Math Problems Worth $1 Million Each

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.

Is there something you're curious about? Send us a note or email us at editors (at) curiosity.com. And follow Curiosity on Facebook, Instagram and Twitter.

Watch And Learn: Our Favorite Content About Math Mysteries

Visualization Of The Travling Salesman Problem

Dijkstra's Algorithm

If you liked this you'll love our podcast! Check it out on iTunes, Stitcher, Google Play Music, SoundCloud, search 'curiosity' on your favorite podcast app or add the RSS Feed URL.

Advertisement