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.

. Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity.

 is reversed.

See also

• 2-opt

• Local search

• Lin–Kernighan heuristic

References

Further reading