2-opt is a simple local search algorithm for the traveling salesman problem, first proposed by Croes in 1958 building on a move already suggested by Flood. It works by taking a route that crosses over itself and reordering it so that it no longer does, comparing every valid combination of the swap, and the technique also applies to related problems such as the vehicle routing problem and its capacitated variant with minor modification.
Facts
Time Complexity
Time Complexity (category)Quadratic Time -- O(n^2) 1 Classification
Design TechniqueHeuristic or Approximation 1 Connections
Uses Design Technique
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Sources
1. 2-Opt Algorithm (Wikipedia)
Wikipedia infobox: time complexity quadratic
quadratic
Wikipedia: design technique heuristic-approximation
heuristic-approximation
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.