Lin–Kernighan heuristic
From Infogalactic: the planetary knowledge core
- This article is about the heuristic for the travelling salesman problem. For a heuristic algorithm for the graph partitioning problem, see Kernighan–Lin algorithm.
In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the travelling salesman problem. Briefly, it involves swapping pairs of sub-tours to make a new tour. It is a generalization of 2-opt and 3-opt. 2-opt and 3-opt work by switching two or three paths to make the tour shorter. Lin–Kernighan is adaptive and at each step decides how many paths between cities need to be switched to find a shorter tour.
See also
References
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found.
- Lua error in package.lua at line 80: module 'strict' not found.
External Links
<templatestyles src="Asbox/styles.css"></templatestyles>
 |
This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
<templatestyles src="Asbox/styles.css"></templatestyles>
 |
This applied mathematics-related article is a stub. You can help Wikipedia by expanding it. |
