Christmas Eve night is a bit of a challenge for Santa on many levels, not least how to plan a route around all the cities and towns in the world making sure that he doesn’t miss any. Ideally, he needs to try and find the single most efficient route which would give him a fighting chance of getting to every single boy and girl before Christmas Morning (well, the boys and girls that aren’t on the naughty list at the very least!).
Easy! Santa can get a map, and measure the distances between the towns and cities – his preference being to measure the distances as a straight line (or what he calls “as the sleigh flies”). And then, he uses that information to work out the shortest route…
Well, unfortunately, it’s not quite so simple. This is a famous computer science problem called the travelling salesman problem. And, it is believed that there is no better way of finding the shortest route than simply checking every single possible option (Note, this isn’t quite the same as the problem a Sat Nav has trying to compute a route from A to B, which is a lot easier by comparison).
OK, well that’s fine though isn’t it? We just throw computing power at it then – just try every combination in turn?
Unfortunately, the travelling salesman problem is famous for good reason – and that’s because it doesn’t scale well. If you have just 4 or 5 cities, then trying every combination is fine, but by the time you’ve reached 60 cities, there are more possible combinations than there are atoms in the observable universe (or to put it another way – there are “a lot”). Even using all the computing power currently available on the planet, you wouldn’t finish churning through those combinations until a time so far into the future that it’s predicted all the stars will have burned out by then (at which point, we’re guessing Santa has bigger problems).
So, what do we do? Do we just give up? Well, not just yet – in computer science and mathematics, when we find situations like this, we turn to something called relaxation. That doesn’t mean giving up and going to a spa – but instead removing some of the rules to make the problem easier, solving the easier problem, and then carefully re-adding the rules. For the travelling salesman problem for instance, there’s a couple of rule changes that allow you to easily find the lower bound (that’s the shortest conceivable route, below which you know for certain there aren’t any better routes).
Once you know what the shortest possible route is, you can come up with techniques to create incrementally better routes. And crucially, by knowing how far away you are from the theoretically best possible answer, you at least have a yardstick to measure progress. Using this approach, researchers have managed to calculate a route through every town and city on the planet which we know is definitely within 0.05% of the best possible solution.
Often, people perceive the role of computing as trying to find the single “right” answer to a problem – but sometimes, as in this case, perfect can be the enemy of good. And to bring this back to what we do day to day, Artificial Intelligence is just the same. We are often making predictions using “fuzzy logic” meaning there is no single right answer, but that’s ok, because getting really close is usually good enough.
So, there you go – problem solved! We have found an efficient route, which although maybe not the best possible route, is really, really close. So, is that how Santa does it? No, of course not! He’s magic… 🎅