0
$\begingroup$

Consider the TSP problem. Let $F_n=\{\text{all cyclic permutations $\pi$ on $n$ objects} \}$. Define the neighborhood 2-change of TSP as

$$N_2^n(f)=\{g: g\in F_n \text{ and $g$ can be obtained from $f$ as follows:}\\ \quad\quad\quad\quad\quad\quad\quad\;\;\;\; \text{remove two edges from the tour; then}\\ \quad­\quad\quad\quad\quad\;\, \text{replace them with two edges}\}.$$

What is the cardinality of $N_2^n(f)$?

I start with few examples like $N_2^1(f)=0$, $N_2^2(f)=0$, $N_2^3(f)=3$ but I cannot find it in general.

$\endgroup$
2
  • 1
    $\begingroup$ A suggestion: keep computing for a few more values of $n$ ($n=4,5,6$), then look the sequence up in the OEIS. You should be able to compute it for small values of $n$ by writing a program to exhaustively enumerate all the cases. $\endgroup$
    – D.W.
    Jan 13, 2017 at 6:23
  • $\begingroup$ But I think there should be a closed-form formula for it, no? $\endgroup$
    – Zir
    Jan 13, 2017 at 17:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.