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