61–70 of 147 posts
So NP is like P again. I learned in school 13 is the max and one of my algebra professors advanced it to 15 (in the 80ies). Then came 20, then came 20.000, this is 80k with proof, and at the World TSP page we see the record was 1m. http://webhotel4.ruc.dk/~keld/research/LKH/ The biggest proven optimum is for 3178031 right now. This should be really done with CUDA, not plain C, btw.
Post proof.
Earlier quoted context omitted.
What are you actually expecting here? The solution was found in a few days by the LKH TSP heuristic solver. They spent months (and decades of CPU time) using well-known techniques to bound the specific problem and prove that this was an optimal solution. It’s not something that you can synthesize to a page. They are literally announcing that they verified the heuristic-derived solution. Consider it like any science,…
[flagged]
- Gaia DR2 (1,331,906,450 Stars): https://www.math.uwaterloo.ca/tsp/star/gaia2.html
> "The tour is at most 1.0038 times the length of a shortest-possible route."
If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result? The classic TSP approach is: 1. Hook up all the nodes in some arbitrary path. 2. Cut the path in two places to create three pieces. 3. Rearrange those three pieces in the six possible ways and keep the shortest. 4. Iterate steps 2-3 until no improvement has been observed for a while. This is not guaranteed to be optima…
For each iteration:
apply some randomisation
starting at each place
cut the path in 2..n places
reconnect in the most optimal way
if the new tour is the new best, save
If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result? The classic TSP approach is: 1. Hook up all the nodes in some arbitrary path. 2. Cut the path in two places to create three pieces. 3. Rearrange those three pieces in the six possible ways and keep the shortest. 4. Iterate steps 2-3 until no improvement has been observed for a while. This is not guaranteed to be optima…
Note that the tour itself was found quickly using a heuristic solver ( https://www.math.uwaterloo.ca/tsp/korea/computation.html ), the achievement here and all the computation is to establish that this is the lower bound (assuming I understood correctly). So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that i…
[0] https://en.m.wikipedia.org/wiki/2-opt
[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
[flagged]
If you find this impressive, take a look at the 1.33 billion stars TSP solution provided by the same authors. - Gaia DR2 (1,331,906,450 Stars): https://www.math.uwaterloo.ca/tsp/star/gaia2.html > "The tour is at most 1.0038 times the length of a shortest-possible route."
It would suck to get to bar 51,248 only to find out it's now permanently closed