At the very real risk of taking something fun, applying Computer Science to it, and completely ruining it(????), this week we are taking a departure from our normal blog posts and looking at the science of Christmas...
How Santa goes about his amazing feats through the perspective of computer algorithms… What a rollercoaster ride of fun and excitement that promises to be. Right? right!? erm, you’ve already stopped reading haven’t you…. ????????♂️
Problem 1: How to hire an elf
For those stalwarts that have made it past that enticing introductory paragraph, the first problem Santa has is how he hires his elves. This relates to a branch of computer science called optimal stopping theory. In this case, let’s say Santa’s problem goes something like this:
- Santa needs to hire a new elf, and wants to hire the best possible elf on the market
- He knows he has 100 hopeful elves to interview, each of whom want to be the next big thing and become part of Santa’s operations at the North Pole
- The problem is, that Santa needs to decide immediately after each interview whether he hires the elf or not – once he’s passed over an elf, there’s no going back
The reason this is called “optimal stopping” is that with 100 elves, it might be obvious that you wouldn’t want to hire the first elf you interviewed, no matter how good you thought they were because there are another 99 hopeful elves in the queue waiting to be interviewed – so the chance that the first elf you saw is the best is pretty small. You might therefore instinctively feel that you would want to interview a few elves to get a feel for how good some of them are first before you commit to hiring one.
But, because you can never go back, every elf that you pass over trying to determine where the bar lies in terms of standards, is one less elf in the queue – and if you eventually reach the 100th elf, then you are going to have to hire them no matter what. So then the question becomes, how do you know when to stop?
Fortunately computer science comes to the rescue! This problem is known as the Secretary Problem, presumably because it was being studied in the late 1950s and early 1960s when hiring a Secretary was seemingly more of a concern than elves… (Santa happens to already have a perfectly good secretary, so he said he’s fine with us sticking with elves for now)
The answer to the puzzle is remarkably simple – the optimal solution is to interview the first 37% of the elves (i.e. the first 37 in this example) and hire none of them. After that, you should hire the first elf that you interview that is better than all the others you have already seen. If you get as far as interviewing the 100th elf, then hire that one.
This approach gives you a 37% chance of hiring the best possible elf, and it’s been proved that there is no better strategy. Interestingly, it doesn’t matter how many elves there are to be interviewed – whether it is a hundred, a thousand or a million, the rules are the same – always pass over the first 37%, and after that, hire the first elf that is better than all the others you’ve already seen.
And, this approach doesn’t just relate to interviewing, it is the same if you’re flat hunting in a high demand area for example, and there are other applications that you might be able to imagine (let’s just say, when it was originally conceived it was actually called the fiancée problem – no comment! ????).
Problem 2: Santa’s Route Choice
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… ????
