A Computer Scientist Walks into a Bar
49,687 times exactly
When I first started studying computer science, specifically algorithms and data structures, the Travelling Salesman Problem quickly fascinated me. The problem poses a seemingly basic question, “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” or how can a travelling sales person hit all their destinations and get home in the quickest time. It’s famous among computer scientists for not only difficult to solve, but quickly spirals out of control the bigger the problem gets. In computational complexity theory it’s known as a NP-Hard problem, or in layman’s terms, the larger the problem gets, the more computationally impossible it becomes to find the perfect solution—or even verify one if you stumbled upon it.
As a British person, I am also ancestrally predisposed to being fascinated by pubs. There is a pub for every mood and a pub for every season. Cosy, leather-bound chairs next to a fireplace not wanting to disturb the landlords dog. Hipster microbreweries with overpriced pig snacks and a sour mango ale. Cocktail bars where the music always beats out my intent to have a conversation inside a normal vocal range. A beer garden, preferably by a river, on the only hot UK day of the year. All social situations that beat out almost any other.
An international team of researchers have managed to combine computer science and the pub-u-lar based activities by attempting to find the shortest route between every pub in the UK - all 49,687 of them. Using advanced algorithmic techniques combined with 250 years of cumulative computer processing time spread across hundreds of cores, they not only found the optimal 63,739,687 meter route but mathematically proved that no shorter path exists.
However, it’s not just about giving us Brits the mathematically quickest way of pickling our insides, but how these methods can be applied to a multitude of disciplines from your local postie to sequencing DNA. For now I better start saving money to start the pilgrimage, although if I could somehow figure out the P vs NP issue, it would certainly help the drinking fund.
Here’s the full report: https://www.math.uwaterloo.ca/tsp/uk/index.html