The Lin-Kernighan algorithm is one of the most effective heuristics for the symmetric travelling salesman problem, belonging to the class of local search algorithms that take a tour and repeatedly search its neighborhood for a shorter one until reaching a local minimum. Like the related 2-opt and 3-opt algorithms it measures the distance between tours by the number of edges that differ between them, but unlike those algorithms it has no fixed number of edges to replace at each step, favoring small numbers such as two or three while remaining adaptive.
Facts
Classification
Design TechniqueHeuristic or Approximation 1 Sources
1. Lin-Kernighan Algorithm (Wikipedia)
https://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithmQuote, https://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm
The Kernighan-Lin algorithm is a heuristic algorithm for finding partitions of graphs.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.