# N-Opt

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 $LaTeX: \textstyle (1,2,\dots,n)$ are pair-wise exchanges. The set of exchanges, however, is larger than the set of 2-Opt neighbors. For example, consider $LaTeX: n=4,$ so the original tour is $LaTeX: \textstyle (1,2,3,4).$ 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 $LaTeX: n=2,$ the replacement is unique - that is, once two edges are chosen for removal, there is only one replacement. This is not true for $LaTeX: n > 2,$ and part of the heuristic is to decide what replacement to make.