Santa Claus uses graphs to find the shortest path to deliver Christmas gifts.
THAT’S MATHS: In the course of a single night, Santa Claus has a billion homes to visit. To ensure that every child gets a gift, he needs to pick a smart route. How does he do it? His challenge is called the Travelling Salesman Problem, or TSP. Suppose a salesman based in Dublin must visit Waterford, Cork and Derry, and wants the shortest route. He can pick any city to begin, then either of the remaining two, and finally the last one before returning home. So, he has 3 x 2 x 1 = 6 choices. But some routes are much longer than others. Clearly, he will not go first to Cork, then to Derry and then to Waterford. The salesman can calculate the distance of all six possible routes and choose the shortest. This is the “brute-force” solution of the TSP. But what if there are 10 cities instead of three? Then there are 10 x 9 x 8 x . . . x 3 x 2 x 1 possible routes. The product of the first 10 numbers, called 10 factorial and written 10!, comes to 3,628,800, far too many to check by hand. And for 20 cities it is 20 factorial, which is more than two million million million. The brute force approach is useless: we have to find a smarter way to solve the problem. The TSP is a “combinatorial optimisation” problem. It is easy to state but difficult to solve effectively. The mathematical structure underlying the problem is called a graph: each city is a vertex, and edges are drawn connecting every two vertices. A round-trip of all the cities is called a Hamiltonian cycle, after William Rowan Hamilton, the outstanding Irish mathematician. Hamilton solved a problem of this type when designing a puzzle called the Icosian Game. The goal of the TSP is to minimise the total length of the round trip. Various “heuristic solutions” have been devised: for example, the nearest neighbour algorithm, where we pick the closest city not yet chosen. But none of these is optimal in all cases. Cross-overs can be removed so that the best route does not intersect itself but is a simple curve, like a greatly distorted circle with an inside and an outside. Read the full article on Irish Times.
Keywords: Santa Claus