You’ve got 20 U.S. cities to visit in one big trip. What’s the shortest route you can take?
No, this is not a problem from Ticket to Ride. It’s the traveling salesman problem, a classic math puzzle that, as MIT Technology Review’s arXiv blog explains, actually becomes computationally impossible to do by brute force, once the number of cities is high enough. There are just too many possible routes to calculate. Mathematicians have figured out some optimization equations to solve the problem, but none are perfect.
The arXiv blog highlighted another way. Two computing researchers from the University of the West of England came up with a sort of hypothetical, sticky goo that finds short routes between points when it contracts.
The researchers wrote in their paper that they were inspired by slime mold, a single-celled organism that other researchers have shown is able to solve mazes and other math problems in its search for food. Slime mold doesn’t solve the traveling salesman problem without restrictions on its natural behavior, however. So the researchers coded this hypothetical slimy moldy material that follows certain chemical signals. Like the slime mold, the goo doesn’t know it’s doing math. It’s just doing what it was programmed–either by its DNA (slime mold) or by researchers (hypothetical blob)–to do.
The researchers ran simulations of the goo on a computer, using numbers of cities that are computable by brute force, so they could compare their goo’s solutions to perfect solutions. They found that the goo works almost as well as brute force. You can watch videos of the contracting process on researcher Jeff Jones’ website. Find Jones and his collaborator Andrew Adamatzky’s paper on arXiv, a website for sharing math and physics papers before they’re peer reviewed.
The goo approach doesn’t work for all city layouts, but for the routes it is suited for, it’s simpler than optimization processes, Technology Review reported. Plus, it’s pretty fascinating to watch.