2 ms·

Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html https://www.math.uwaterloo.ca/tsp

Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html 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 it is considerably more advanced for good reasons, randomly picking will take too long to converge).

n4r9 1y ago
The algorithm that OP describes is more commonly known as 2-opt [0]. The heuristic used in this case is referred to as LKH which I assume means the Lin-Kernighan Heuristic [1]. The latter is sort of a meta generalisation of the former. [0] https://en.m.wikipedia.org/wiki/2-opt https://en.m.wikipedia.org/wiki/2-opt [1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
- vjerancrnjak 1y ago
  2-opt is a bit simpler. LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/