The news recently revealed that clever people at the University of Waterloo in Ontario, Canada, have made progress with the Travelling Salesperson Problem. The good folk in Waterloo used algorithms to find the shortest crawl around almost 25,000 pubs in Britain (28,270 miles, in case you were wondering). This really restores my faith in academia that the might of our collective brainpower is employed on worthwhile tasks.
The TSP you may remember, if you had been bothered to read my book which is still astonishingly good value at www.atried.com/shop, is one of the great unsolved mysteries of modern mathematics. I used to teach it in my previous existence at sixth form college and, strangely for a mathematician perhaps, loved the idea that there wasn’t a definitive answer.
In thousands of years of scientific advancement we can put a man on the moon and a driverless car on the road, and yet we can’t tell a travelling salesperson how to visit 100 destinations in the shortest distance. In this age when it is public knowledge what Justin Bieber had for breakfast, it is exciting that there are still things to be discovered.
“Am I bothered?” you may rightly ask.
“Yes” is my simple response.
Firstly, it would help greatly with future tours of British racecourses, finding the optimum route between the venues. Those entertaining thoughts of unusual variations on my equine theme would do well to complete the pub crawl in eighty days, but if you are at a loose end it and fancy a pint or 25,000, it would certainly come in rather useful.
Secondly, if you happen to find “the answer” down the back of the sofa it would be worth an enormous sum of money. The Clay Institute in America has nominated The Travelling Salesperson as one of its ten millennium puzzles with a prize of $1m to the first person to solve it. However, patent it first because in all honesty it would be likely worth billions to industry – think about how many delivery vans hit the roads every day!
To clarify, the human race hasn’t been entirely defeated on the matter. To solve the earlier example of 100 destinations by brute force – looking at each possible tour and selecting the shortest – would take literally billions of years. However, there are a number of advanced algorithms (such as the ones used at Waterloo), far too complicated for an ex-A level maths teacher to understand, that have appeared over the years as people realise the enormous value of a solution.
These new techniques do rather well with surprisingly large numbers of destinations, but they are certainly not the elegantly simple algorithms that anyone could use to solve problems such as the shortest route between two towns (a subtly different proposition) and often require significant computing power and expensive downloads (do you really think they are going to give it away when it could save corporations like Amazon billions?)
So I refuse to invest in an answer to my own racecourse tour. My real-life version of last year was no doubt a gross distortion of the optimal solution, but it was what it was and I would not now have it any other way. Newton Abbot to Newbury, and Perth to Plumpton would be unlikely to feature in any computer generated answer, but they existed in a far more immediate and personal way in my own absurd and mathematically-imperfect version of reality.
I have attempted all the racecourses of Britain in eighty days and all the poker tournaments on the Las Vegas Strip in eighty hours. Friends have discussed the feasibility of watching matches at all 92 English football league grounds in 80 days (difficult because of international breaks, but perhaps possible if you include reserve team matches?) Canadians have kindly highlighted a route that, if you had a stout pair of walking boots and an extraordinarily high alcohol tolerance, would take in all the British boozers in, say, ten years.
What else is out there, as yet undiscovered or even considered, in the vast variety of our endless universe? Like the Travelling Salesperson Problem, there must be incalculable possible tours just waiting to be dreamt up.