Last week I eulogized the used car salesman. Today, we look at computing’s most famous salesman: The Travelling Salesman.
You are a travelling salesman, selling fine, hand-drawn maps with gilded edges. (In the post-GPS world, the only way you are selling maps is if they are a nostalgic “craft” brand – like a microbrewery for maps). You want to visit as many cities as you can, thereby maximizing the number of sales you can make. (Selling door-to-door will really help push the retro angle on your product). You pull out one of your maps and begin to plan your trip. The map has all the cities in the country on it, and distance between them. You are bold. You will visit every city in the country! You need to end up back in your hometown when you are done, and you want to spend as little time on the road as possible for maximum efficiency. You study the map for a while and come up with a travel plan – that is, a route that takes you through every city. You are happy.
Excited, you explain your plan to a friend. Your planned trip will take you three months. Your friend nods, but then draws up a new plan. The new plan will also take you through every city, but will only take two months; clearly this is a better use of your time. You were sloppy. Your original plan seemed reasonable, but certainly this new one is much better. Then your friend asks: maybe you could cut another week off your trip and still hit every city? You don’t know. Is this new plan the best travel plan possible? Is there an easy way to tell? You have a bad case of the Travelling Salesman Problem.
The Travelling Salesman Problem is perhaps the well most publicized “hard computer science problem” in part because…
The Travelling Salesman Problem is perhaps the well most publicized “hard computer science problem” in part because it is legitimately important, but also because it has a cool name, (see also: Neural Network). If you ever read a popular article about computation complexity, it will be about the Travelling Salesman Problem and not about Minimum Cut or Vertex Cover. In fact, it’s happening right now. You are reading a popular article about computation complexity and I am telling you all about Travelling Salesman and I’m not touching anything else until those other problems get a better marketing department and rebrand themselves with slick metaphors.
So, double checking every possible route to make sure you find the best one is pretty tedious. Sounds like a job for a computer, right? If Garmin and Google can tell you the shortest path to the grocery store, surely they can bang this one out too? I’ve already spoiled the surprise by calling this a hard problem, but yes, it turns out this is a much more complicated question than just asking for the shortest path. For quick intuition as to why: it is because you are specifying what cities need to be on your path, but you aren’t specifying an order to visit them in. You just need to visit all of them, in any order. As it happens, your computer isn’t much more enthusiastic about solving this one than you are.
But aren’t they doubling in power every so many years? Can’t they just gobble this up? You spend your whole day watching computers gobble everything up, so maybe it seems anathema to learn that a) There are things that cannot be computed and b) There are things that cannot ever be computed quickly. Consider your planning problem above, consider adding a new city to your map, and then consider how much harder you just made the problem. The Travelling Salesman problem scales very badly.
A common misconception about computers is that they can just “brute force” anything. This is often how chess computers are described, as looking ahead a bunch of turns and picking the best move. This isn’t an inaccurate description, but it glosses over the fact that you can’t look ahead very many turns at all before making your decision takes an inappropriately long amount of time.
Should you care? Is this just an annoying problem computer nerds made up to taunt you with? Most such problems are just abstractions of situations that occur in real life. If you have a machine that needs to solder a bunch of points on a board, and you want it to do as many boards as it can, that’s Travelling Salesman. Laying out the plumbing for a home, (or a neighborhood), and you want to reach every fixture with as few pipes as possible? Trick question, that is not Travelling Salesman, (The key difference is that the water isn’t making a tour of every fixture, you are allowed to branch your path). The plumbing problem is much easier to solve. I bring it up because computational complexity is a tricky thing. Two problems can look very similar, and yet one can be intractably hard and the other can be easy.
The big takeaway that I’m aiming for is that computers are not a panacea for any and all number crunching or planning you would want to do. For all that they seem to have given us, we are often exasperated by what they can’t do, and the typical response is that “someone should figure out how to make it do that.” The humbling response is that sometimes it truly can’t be done.