4 ms·
Just a side note: The mentioned Christofides algorithm only works for metric TSP. In metric TSP the edges satisfy triangle inequality. There doesn't exist any
by Scea91 11y ago
Just a side note:
The mentioned Christofides algorithm only works for metric TSP. In metric TSP the edges satisfy triangle inequality.
There doesn't exist any polynomial approximation algorithm for general TSP. If it existed we would be able to solve existence of Hamiltonian circuit in polynomial time by a simple reduction and therefore would be able to prove that P = NP.
- gus_massa 11y agoI agree. Another side note. From the article: > Note that we are making the simplifying assumptions that the Earth is a perfect sphere, and that the distance is a simple Euclidean distance, instead of a driving distance. Although one can certainly plug in a different distance metric and follow the same procedure outlined here. I think that the deformation of the Earths surface are not important, and just change the values but not the metric properties. But the driving distance (or driving time) are not long a metric, in particular the driving distance between A and B is not equal to the driving distance between B an A. Anyway, the superchargers are so far away that the polynomial algorithm will give the correct result (probably).
- chiph 11y agoI think that the deformation of the Earths surface are not important This probably only matters if the distances are larger. Probably larger than the distance a Tesla can go on a single charge. And so can be dropped from consideration.
- greglindahl 11y agoIt's important to take into account up/down distances and wind conditions to accurately estimate energy consumption (or range) of a Tesla over a given route.
- mrgoldenbrown 11y agoThank you for this clarification - I was quite surprised when I read that "1.5 times optimum" sentence.