ALGORITHM ARTICLE
Nearest neighbour + 2-opt
Problem. Fast construction and local improvement of a feasible TSP tour.
Core idea. Build greedily, then reverse segments that reduce two-edge cost.
Procedure
- Visit the nearest unseen vertex.
- Close the tour.
- Repeat improving 2-opt reversals.
Certificate. Feasible permutation with recomputed cost.
Data structures and API
from optfin_orlab.tsp import TSP
solver = TSP()
result = solver.heuristic(...)Complexity. O(n³) in the simple implementation
Limits. Local optimality is not global optimality.
OPTFIN AUDIT CHECKS
What has to reconcile before this method is trusted.
- DefinitionProblem, objective, inputs and output are explicit.
- Data structureThe public API and canonical source path are identified.
- CorrectnessFeasible permutation with recomputed cost.
- ComplexityO(n³) in the simple implementation
- Operational limitLocal optimality is not global optimality.
- ReproductionSource, executable test and evidence route remain linked.
LUNA ACADEMIC
Continue this algorithm in one research conversation.
Ask for the paper trail, executable test, source explanation, or a reproducibility plan for Nearest neighbour + 2-opt.
Open Luna for this algorithm