Overview
2-Opt applies reversing crossing tour segments when the swap shortens the tour to handle traveling salesperson improvement with a named, inspectable procedure.
CoreSource checked
2-Opt
2-Opt uses reversing crossing tour segments when the swap shortens the tour for traveling salesperson improvement.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Local Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
traveling salesperson improvementlocal searchoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(n^2)
Worst
O(n^3)
Space
O(n)
When to Use
- Use 2-Opt when solving traveling salesperson improvement and you want to benefit from 2-Opt uses reversing crossing tour segments when the swap shortens the tour for traveling salesperson improvement.
- Choose it when O(n^2) average/worst-case time and O(n) memory match your workload profile.
- Prefer it over Held-Karp TSP or Christofides Algorithm when the problem structure favors traveling salesperson improvement.
When Not to Use
- Avoid when exact optimality is required but the method is heuristic or approximate.
- Avoid when constraints are poorly defined or cheap feasibility checks are unavailable.
What It Does
- 2-Opt uses reversing crossing tour segments when the swap shortens the tour for traveling salesperson improvement
- Organizes the work around traveling salesperson improvement and local search.
Use Cases
- Production and research workloads requiring traveling salesperson improvement via 2-Opt uses reversing crossing tour segments when the swap shortens the tour for traveling salesperson improvement.
- Local Search pipelines where O(n^2) time and O(n) space fit system constraints.
- Engineering comparisons against Held-Karp TSP and Christofides Algorithm when tuning traveling salesperson improvement.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Pseudocode
- 1.Formulate the traveling salesperson improvement instance, objective function, and initial candidate state or active search tree.
- 2.Evaluate candidate feasibility and objective bounds (traveling salesperson improvement, local search).
- 3.Advance the search by 2-Opt uses reversing crossing tour segments when the swap shortens the tour for traveling salesperson improvement.
- 4.Prune suboptimal branches, propagate unit/conflict clauses, or update incumbent best solutions.
- 5.Return the optimal or best-found feasible assignment once convergence or exhaustion is reached.
Canonical Example
- Input
- Objective, constraints, and candidate variables configured for a representative traveling salesperson improvement test case
- Output
- Best known feasible solution satisfying 2-Opt invariants
- Explanation
- 2-Opt processes the input by 2-Opt uses reversing crossing tour segments when the swap shortens the tour for traveling salesperson improvement, tracking traveling salesperson improvement and local search to produce the verified traveling salesperson improvement result.
Implementation Notes
- State the objective and feasibility checks in code before adding pruning.
- Keep incumbent solutions separate from bounds.
- Add tests for infeasible and exactly-tied cases.
Common Pitfalls
- Assuming a heuristic is exact without checking its guarantee.
- Using weak bounds that make search behave like brute force.
- Forgetting infeasible, empty, or degenerate constraint cases.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow reversing crossing tour segments when the swap shortens the tour on a small traveling salesperson improvement example.
Step 1 of 5: Formulate the traveling salesperson improvement instance, objective function, and initial candidate state or active search tree.
optimization-mechanismNotes
2-Opt operates in O(n^2) time and O(n) space within the Local Search family. Often compared with Held-Karp TSP and Christofides Algorithm.
Sources (2)
What each reference supports for this entry.
The Traveling Salesman Problem: A Computational Study
BookTSP reference for 2-Opt's tour construction, local-search neighborhood, or heuristic tradeoffs.
Croes 2-Opt
PaperEarly reference for 2-opt style edge-exchange improvements for the traveling-salesman problem.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toChristofides Algorithm
Optimization · Core
Both address traveling salesperson improvement, but they make different modeling or performance tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toHeld-Karp TSP
Both address traveling salesperson improvement, but they make different modeling or performance tradeoffs.
Alternative toChristofides Algorithm
Both address traveling salesperson improvement, but they make different modeling or performance tradeoffs.
Alternative toNearest Neighbor TSP
Both address traveling salesperson improvement, but they make different modeling or performance tradeoffs.
Related Algorithms
Tags
Optimization