3 ms·
> There are more sophisticated approximate algorithms that can handle hundreds of thousands of cities and come within 0.01% or better of the shortest possible t
by brador 12y ago
> There are more sophisticated approximate algorithms that can handle hundreds of thousands of cities and come within 0.01% or better of the shortest possible tour.
Anyone have more details on this more sophisticated algorithm? Even just a name to google would be great.
- JadeNB 12y agoj2kun gives a link below: https://news.ycombinator.com/item?id=9481527 https://news.ycombinator.com/item?id=9481527 .
- _delirium 12y agoThe earliest one to be proposed (1958) is called "2-opt": https://en.wikipedia.org/wiki/2-opt https://en.wikipedia.org/wiki/2-opt The Lin-Kernighan heuristic is a related heuristic developed later, which works well in practice on many problems. Here is an implementation (freely available source, but not freely licensed): http://www.akira.ruc.dk/~keld/research/LKH/ http://www.akira.ruc.dk/~keld/research/LKH/