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⊠đ
Related posts
How businesses are reducing operational costs with AI
AI is revolutionising business operations by automating tasks, improving decision-making, and cutting costs. This blog explores case studies from manufacturing, retail, energy management, financial services, and healthcare, showcasing AI’s impact on efficiency and cost reduction.
Boosting Sales with AI: What the Numbers Say
AI is transforming sales by automating processes, personalising customer interactions, and optimising strategies. Tools like chatbots and recommendation systems boost conversions, with personalised recommendations increasing sales by 35% and chatbots enhancing engagement and conversions by 20%. AI also improves lead scoring and real-time data analysis, significantly raising conversion rates and revenue across industries.