Hacker News Reader

There are also TSP-specific heuristics that work well in practice on a lot of large instances, often finding the optimal solution pretty quickly (but with no guarantees of optimality). The first I believe was the Lin-Kernighan heuristic from 1973 (the same Kernighan as the 'K' in K&R C, incidentally). There are fast implementations of some modern improved versions, e.g.: http://akira.ruc.dk/~keld/research/LKH/

View on HN

I coded a version of SA for TSP in the early 90s. I iterated until the probability of a hardware error was greater than having a sub-optimal solution. It took just a couple of seconds, and that speed was due to visually displaying the algorithm as it executed.

I believe that this is about a different type of TSP problem, where the distances between cities are defined by the geometric distance from their coordinates in some plane (or on a sphere). This is a simpler problem than when the distances are specified as (whole) numbers.

Geometric distance implies symmetry, asymmetric TSP can be converted to symmetric by doubling the number of vertices.

Reply on news.ycombinator.com