In optimization, 3-opt is a simple
local search heuristic for finding approximate solutions to the
travelling salesperson problem and related
network optimization problems. Compared to the simpler
2-opt algorithm, it is slower but can generate higher-quality solutions.
3-opt analysis involves deleting three edges from the current solution to the problem, creating three sub-tours. There are eight ways of connecting these sub-tours back into a single tour, one of which consists of the three deleted edges. These reconnections are analysed to find the optimum one. This process is then repeated for a different set of 3 connections, until all possible combinations have been tried in a network. A single pass through all triples of edges has a time complexity of
.
Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity.
See also
*
Lin–Kernighan heuristic
References
Further reading
*
*
*
* {{cite book , last=Sipser , first=Michael , title=Introduction to the theory of computation , publisher=Thomson Course Technology , publication-place=Boston , date=2006 , isbn=0-534-95097-3 , oclc=58544333 , page=
Heuristic algorithms
Travelling salesman problem