logoalt Hacker News

n4r904/24/20251 replyview on HN

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...


Replies

vjerancrnjak04/24/2025

2-opt is a bit simpler.

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