Sorry folks, I haven’t had time to write a CS-based Christmas story this year so here’s one from a few years ago!
Merry Christmas!
Tag Archives: Travelling Salesman Problem
The Travelling Santa Problem
Why is the annual Father Christmas world tour ‘NP-Complete’? What is ‘NP-Complete’ anyway? In fact, what’s ‘NP’ even? And why can only Santa do it? And what’s a ‘Decision Elf’? And just how awesome is Rudolph’s nose? What’s ‘Inspirational Magic’? This and so much more you didn’t know about the annual Christmas Eve ritual …
We all know the problem well enough … Father Christmas has to travel around the world, visiting all the good girls and boys, in a single night, and return to where he started at the North Pole. Sounds like a tall order! Can it be done?
Are There Any Hard Problems?
That looks like a hopelessly vague question, and it is unless we’re prepared to clarify it a bit. On the other hand, we already know there are some impossible problems so surely there are some that are just hard? Again, we’ll need to work out what on earth we’re talking about here. Let’s start with what we actually mean by a problem in a computational sense …
(Be warned: There are one or two simplifications and liberties with precision in what follows; it’s well-intentioned but may upset the purist.)
Well, actually, even that isn’t simple and there’s no absolute agreement on what a good definition would be. (We’ve seen previously that mathematicians and computer scientists don’t always see eye-to-eye.) It’s cheating a bit but it’s probably easier to give examples and this should work well enough for us. At least in the context of computing, these are all valid problems:
- Calculate 2 x 4 + 9 – 3
- If 5 – x = 2 what’s x?
- Find the largest from 5, 7, 1, 4, 8, 5, 2, 4, 8, 5, 2, 6, 7, 7, 3, 3, 2, 4, 3, 6, 7, 7, 6, 5, 4
- Sort 25, 44, 66, 72, 12, 45, 56, 90, 45, 69, 11, 10, 12, 42, 88 into ascending order
- Arrange 1, 2, 3, 4, 5, 6, 7, 8, 9 into a magic square
- What’s the best way to get to Paris?
Under the lamp
Turing's Radiator 