Metraipolis › archive › dc_90e7abde3cbf
3-opt — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/3-opt
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-06T12:46:20.058Z
- SHA-256 of the archived text
bf3f6a6e6b5e7b9c56e8d06358a07644fafc506a54f8f1ce72db88cef494131a- Stable URL of this page
https://metraipolis.com/documento/dc_90e7abde3cbf
How to cite
3-opt — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/3-opt (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_90e7abde3cbf (Metraipolis archive dc_90e7abde3cbf, sha256 bf3f6a6e6b5e7b9c56e8d06358a07644fafc506a54f8f1ce72db88cef494131a)
BibTeX
@misc{dc90e7abde3cbf,
title = {3-opt — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/3-opt},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_90e7abde3cbf; sha256 bf3f6a6e6b5e7b9c56e8d06358a07644fafc506a54f8f1ce72db88cef494131a},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/3-opt. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 O ( n 3 ) {\displaystyle O(n^{3})} . Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity. In an array representation of a tour with k {\displaystyle k} nodes S = [ n 0 , n 1 , n 2 , . . . , n k − 1 , n k ] {\displaystyle S=[n_{0},n_{1},n_{2},...,n_{k-1},n_{k}]} , where n 0 = n k {\displaystyle n_{0}=n_{k}} , deleting three edges separates S {\displaystyle S} into four segments S 1 {\displaystyle S_{1}} , S 2 {\displaystyle S_{2}} , S 3 {\displaystyle S_{3}} and S 4 {\displaystyle S_{4}} . Note that the segments S 1 {\displaystyle S_{1}} and S 4 {\displaystyle S_{4}} are connected. The reconnection of the Subtours is done by a combination of reversing one or both of S 2 {\displaystyle S_{2}} and S 3 {\displaystyle S_{3}} and switching their respective positions. The 8 possible new tours are [ S 1 , S 2 , S 3 , S 4 ] {\displaystyle [S_{1},S_{2},S_{3},S_{4}]} , [ S 1 , S 2 ↔ , S 3 , S 4 ] {\displaystyle [S_{1},{\overleftrightarrow {S_{2}}},S_{3},S_{4}]} , [ S 1 , S 2 , S 3 ↔ , S 4 ] {\displaystyle [S_{1},S_{2},{\overleftrightarrow {S_{3}}},S_{4}]} , [ S 1 , S 2 ↔ , S 3 ↔ , S 4 ] {\displaystyle [S_{1},{\overleftrightarrow {S_{2}}},{\overleftrightarrow {S_{3}}},S_{4}]} , [ S 1 , S 3 , S 2 , S 4 ] {\displaystyle [S_{1},S_{3},S_{2},S_{4}]} , [ S 1 , S 3 ↔ , S 2 , S 4 ] {\displaystyle [S_{1},{\overleftrightarrow {S_{3}}},S_{2},S_{4}]} , [ S 1 , S 3 , S 2 ↔ , S 4 ] {\displaystyle [S_{1},S_{3},{\overleftrightarrow {S_{2}}},S_{4}]} and [ S 1 , S 3 ↔ , S 2 ↔ , S 4 ] {\displaystyle [S_{1},{\overleftrightarrow {S_{3}}},{\overleftrightarrow {S_{2}}},S_{4}]} . Here S i ↔ {\displaystyle {\overleftrightarrow {S_{i}}}} indicates that segment i {\displaystyle i} is reversed.
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico).
Fonte: Wikipedia in inglese, voce «3-opt» — https://en.wikipedia.org/wiki/3-opt
Wikidata Q4634247: «search algorithm» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4634247
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/3-opt?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1341143907, consultata il 2026-11-06T12:41:36.837Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b4a7071816c0677f17606df16f6f5cf2931af7a8102351d0b8c3929817127abb