3 ms·
Ummm no. You read only the first few sentences. Google sought out to also solve the TSP and used the 50 year old Christofides algorithm which is built on top of
by heimatau 10y ago
Ummm no. You read only the first few sentences. Google sought out to also solve the TSP and used the 50 year old Christofides algorithm which is built on top of Euler's bridge problem (graph theory) solution.
- rdiddly 10y agoGuilty as charged - and worse: all I cared about was the source of the 280 years figure, as used in the disingenuous and clickbaity phrase "280-Year-Old Algorithm." I was being all meta. Edit: Also a variation on the TSP was part of my senior project so I am forever traumatized.
- zump 10y agoIs there an exact solution to the TSP?
- beagle3 10y agoOf course. But it's O(n*2^n) at best, IIRC (The trivial is O(n!) - just test all orders) There are simple <=2x and slightly more complicated <=1.5x guaranteed approximate solutions on metric spaces, but on most spaces there aren't even approximate solutions.
- AstralStorm 10y agoIt so happens that a map is a metric space. Euclidean metric. If you want to include transport, change it to optimal travel time metric. (Requires evaluating optimal travel time in the tested vicinity first. There are nice and fast algorithms to do it, starting with variants of A* and IDDFS.)
- glaberficken 10y agoIf you have interest in this, I suggest this amazing iPython notebook by Peter Norvig: http://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb http://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb