|Santa's Dilemma (or the Travelling Salesman revisited)
||[Dec. 5th, 2003|03:10 pm]
I made a passing reference to the "Travelling Salesman" problem in an e-mail yesterday but had forgotten the name attributed to it.
The "problem" can be expressed in words from the following page devoted to finding least cost alternatives
The Travelling Salesman Page
The travelling salesman problem, or TSP for short, is this: given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point.
"Old Saint Nick has one night to deliver gifts to children around the world. To save time and wear and tear on his sleigh, Santa plots the shortest journey possible among thousands of cities."
I don't believe Santa Claus is known for his mathematical ability and (from evidence obtained) his gift giving appears to be very discriminatory, focussing on the well-off in society and ignoring the poorer and possibly "less believing".
Despite his red clobber he's probably a died in the wool conservative :-)