the-travelling-santa-problem

 

Christmas time is here and all of us, in Pressidium, have been working fervently behind the scenes to keep everything humming. At times,when we grow despondent (perhaps a little bit grumpy) we remind ourselves of all the things we are grateful for. We also remind ourselves that some others have it way more difficult than we do. And that includes Santa as well. No, we are not talking about some family impostor. We do mean the real one! You know. Red costume, white beard, chubby guy veering an 8-reindeer-powered, flying sleigh? Santa may have lots of elves and a big fat belly, but the logistic problems he needs to tackle with every year are very, very complex. (And since his myth is based on a 4th century Greek bishop, then he probably knows how to keep tabs).

The Problem

But what problem does Santa have to deal with? Imagine that we have a vast network of points and lines; with points representing children (Wolfram Alpha estimated them to be 1.847 billion in 2010) and lines representing the distance between. Santa needs to calculate the shortest path between all the cities and the children’s chimneys.

Santa may try every different route he can until he maps out the shortest, but this is grossly inefficient. As the chimneys and the cities to visit increase, so do the possibilities of different routes to take. Santa’s plan goes something like this:

  1. Depart from Santa’s Headquarters at the scheduled time.
  2. Visit all cities and chimneys through the shortest route.
  3. Don’t visit any spot twice.
  4. Return to Santa’s Headquarters (in time for the family dinner).

The increase happens in a dramatic (exponential) way.  The number of possible routes for an n amount of cities is n! (For example, for 5 cities you would get 5 * 4 * 3 * 2 * 1 = 120 routes) Below is a table summarizing the exploding number of routes that Santa needs to try, as the cities increase:

factorial-montseratt-png

We are still under 100 cities and the number of routes that Santa needs to try is mind blowing. This is without calculating the different number of chimneys in each city!

To understand just how mind boggling the number becomes, you should consider this: If there was a computer that could test 1 million routes per second, and that computer crunched away for a period equal to the age of the universe, it would successfully solve The Travelling Santa Problem of only 23 cities!

So then, how many times the age of the universe would the computer take to test all the possible routes? For a problem the size of a city alone it would take approximately 10 to the power of a 9 digit number. So not possible. Ever.

 

But..Santa Claus does not exist nor do any of his problems!

Although the verdict might still be out for some people regarding the existence of Santa Claus, the above problem remains very real. It is a variation of a problem called The Travelling Salesman Problem (TSP), sporting a salesman instead of Santa. Quite curiously both share the same initials (did you notice that?).  It is a classic computer science problem in optimization. Its practical applications range from scheduling transportation truck routes to testing digital circuits and genome sequencing.

Although some might not care about Santa's problems, people do care when it comes to transportation, DNA and stuff. Because the problem was very difficult (in computer science terms, NP-hard) and it could not be solved by brute force, another approach was followed. Throughout the years, computer scientists have been inventing approximation algorithms. These algorithms use heuristics to solve problems with millions of cities. The solutions that come up  have a high probability of  being "good enough" to these problems (they are efficient and reduce energy consumption).

There were even some scientists solving the problem by using a family of algorithms called Ant Colony Optimization (ACO). The initial idea was based on the behavior of ants while they foraged food sources and traveled back and forth to the colony, slowly creating a network of pheromones. By inspecting the pheromones left behind, one could compute a good path between that source of food and the ant colony.

 

What we really want to say

Computer science might come off as a dry subject to some, but we find that some of its problems are quite parallel to real life. We all face "insurmountable" problems from time to time, just like the TSP one. Our problems might not involve scheduling tours or testing circuits, but the feeling is the same. Life is vague and not as clear-cut as numerical problems.

But maybe what we've learned in Computer Science could be applied to the intractable problems of Life. In those situations, one needs to cut corners, improvise, and settle for the "good enough" solution. Otherwise analysis-paralysis occurs, and you end up doing nothing, grinding away at all 10^64 possible courses of action. Sounds familiar? We've all been there. Ants, though, just keep on going.

OK, we don't leave chemical trails behind our mistakes but I am sure that you do get the idea:

Go out, follow your nose and do what you want! Today, not tomorrow! Don't expect it to be perfect because sometimes "good enough" will do. Don't worry about mistakes either, because we got you covered. No matter what breaks. It's like having your own Little Helpers. Go out and explore!

Merry Christmas from all of us here in Pressidium!

 

 

Categories: Announcements

Subscribe to Pressidium's Blog

Did you like this article? Get Pressidium's latest blog articles straight to your inbox.