Edited by Richard Walker, Sunday, 7 June 2020, 01:58
I was reminded of this today by a friend and colleague. The TSP problem asks how to calculate the shortest round trip between a set of cities, given the respective distances between them.
Simply comparing all the possible routes one after another will obviously work, but with even a few cities, and the fastest computer in existence, it could take thousands or millions or more years. So is there a way to solve it in a feasible length of time?
The TSP attracts a lot of attention, because it’s easily stated and most people have a gut feeling there should be a lightbulb intuition that will show the way. However decades of professional and amateur endeavour have not succeeded. We have good ways to calculate it well enough for delivery services say, but no way of finding the absolute optimum until the customer is long dead. Amazon and Google and others use algorithms which are good enough, and they are good enough; shaving 100 metres off a delivery trip will avail nought if there is a parked car en route.
So it’s a theoretical question, but to my mind they are the ones that we learn most from.
Let XKCD have the last word. This is the approach that will probably work best in this year of crisis, and perhaps at all times.
Travelling Salesman Problem
I was reminded of this today by a friend and colleague. The TSP problem asks how to calculate the shortest round trip between a set of cities, given the respective distances between them.
Simply comparing all the possible routes one after another will obviously work, but with even a few cities, and the fastest computer in existence, it could take thousands or millions or more years. So is there a way to solve it in a feasible length of time?
The TSP attracts a lot of attention, because it’s easily stated and most people have a gut feeling there should be a lightbulb intuition that will show the way. However decades of professional and amateur endeavour have not succeeded. We have good ways to calculate it well enough for delivery services say, but no way of finding the absolute optimum until the customer is long dead. Amazon and Google and others use algorithms which are good enough, and they are good enough; shaving 100 metres off a delivery trip will avail nought if there is a parked car en route.
So it’s a theoretical question, but to my mind they are the ones that we learn most from.
Let XKCD have the last word. This is the approach that will probably work best in this year of crisis, and perhaps at all times.
https://xkcd.com/399/