# N-Opt

### From Glossary

This is a heuristic for the TSP, though it can apply more generally to a problem that seeks a subgraph with all nodes. It is a local search, which considers a *move* by removing *n* edges from a trial solution, then replacing them with some other *n* edges. In TSP, the 2-Opt *neighbors* of the tour
are pair-wise exchanges. The set of exchanges, however, is larger than the set of 2-Opt neighbors. For example, consider so the original tour is
The six pair-wise exchanges of this permutation are:

(2,1,3,4): (1)*--(2) (3,2,1,4): (1)*--(2) \ * | * \/ | | /\ | | / * * | (4)*--(3) (4)--*(3) (4,2,3,1): (1) (2) (1,3,2,4): (1) (2) |* * | |* * | | \/ | | \/ | | /\ | | /\ | */ \ * */ \ * (4) (3) (4) (3) (1,4,3,2): (1)*--(2) (1,2,4,3): (1)--*(2) | * * / | | \/ | | /\ * | * \ (4)--*(3) (4)--*(3)

We see duplicates due to the equivalence of any cyclic permutation. Also, there are only two 2-Opt moves if the TSP is symmetric:

(1)---(2) (1) (2) \ / |\ / | \/ | \/ | /\ | /\ | / \ |/ \ | (4)---(3) (4) (3)

For the replacement is unique - that is, once two edges are chosen for removal, there is only one replacement. This is not true for and part of the heuristic is to decide what replacement to make.