3-opt
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 .[1] Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity.
See also
[edit]References
[edit]- ^ Blazinskas, Andrius; Misevicius, Alfonsas (2011). Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem (PDF). 17th International Conference on Information and Software Technologies. Kaunas, Lithuania. S2CID 15324387.
Further reading
[edit]- BOCK, F. (1958). "An algorithm for solving traveling-salesman and related network optimization problems". Operations Research. 6 (6).
- Lin, Shen (1965). "Computer Solutions of the Traveling Salesman Problem". Bell System Technical Journal. 44 (10). Institute of Electrical and Electronics Engineers (IEEE): 2245–2269. doi:10.1002/j.1538-7305.1965.tb04146.x. ISSN 0005-8580.
- Lin, S.; Kernighan, B. W. (1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research. 21 (2). Institute for Operations Research and the Management Sciences (INFORMS): 498–516. doi:10.1287/opre.21.2.498. ISSN 0030-364X.
- Sipser, Michael (2006). Introduction to the theory of computation. Boston: Thomson Course Technology. ISBN 0-534-95097-3. OCLC 58544333.