Hacker News new | ask | show | jobs
by amscanne 423 days ago
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 it is considerably more advanced for good reasons, randomly picking will take too long to converge).
1 comments
n4r9 423 days 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

[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...

link
vjerancrnjak 423 days ago
2-opt is a bit simpler.

LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/

link