8
$\begingroup$

SO the general answer I come across on the internet is $(n-1)!/2$. But it would seem to be $n!$, or at least $(n-1)!$. Which one is it?

If you have 2 cities, you would have 1 path. So $(n-1)!/2$ can't hold?

EDIT: Another question. Let $P$ be the transition matrix between the routes according to the 2-opt procedure.

The pairwise exchange or 2-opt technique involves iteratively removing two edges and replacing these with two different edges that reconnect the fragments created by edge removal into a new and shorter tour.

The transition probabilities $P_{kl}$ for given $k$ and $1\leq l \leq size(P)$ can only take two values. What are the two value? I guess $P_{kk} = 0?$

$\endgroup$
3
  • $\begingroup$ Is the link ams.org/samplings/feature-column/fcarc-tsp? $\endgroup$
    – user122283
    Mar 24 '14 at 22:53
  • $\begingroup$ What is the problem? $\endgroup$
    – user137500
    Mar 24 '14 at 22:53
  • 3
    $\begingroup$ You are correct; the $(n-1)!/2$ formula holds only for $n\ge 3$. $\endgroup$
    – MJD
    Mar 24 '14 at 23:03
7
$\begingroup$

There are $(n-1)!/2$ possible tours in the undirected form of the problem - $(n-1)!$ instead of $n!$ since it doesn't matter which node you start at, and you divide by two since e.g. for three nodes $A, B, C$, the tour $A\to B\to C\to A$ is the same as the tour $A\to C\to B\to A$.

I suppose I should add that in the undirected case, it doesn't really make sense to speak of a traveling salesman tour when $n<3$ since there can't be a cycle in the graph (and that's what a traveling salesman tour is, a Hamiltonian cycle).

$\endgroup$
1
  • 1
    $\begingroup$ This analysis is sound for $n\ge 3$, but undercounts when $n\le 2$, which is part of the source of OP's confusion. $\endgroup$
    – MJD
    Mar 24 '14 at 23:02
1
$\begingroup$

So suppose you have $n$ cities, then for any given route, if you remove two edges then you must replace them with their cross matches. For example, lets say you have $$A\rightarrow B\rightarrow C\rightarrow D\rightarrow E$$

Then if you remove $(B, C)$ and $(E, A)$ then you must replace the with $(B, E)$ and $(A,C)$. This replacement is unequivocal.

So for any pair of edges of a tour there is exactly one unequivocal pair of edges as replacement. Furthermore, from every graph of $n$ cities and thus $n$ edges, you can select $$\dfrac{n(n-3)}{2} = \delta$$ pairs of edges which can be replaced by the 2-opt procedure. Why this holds is because, per graph you have the set of all possible pairs of edges minus the ones adjacent to each other. So one can not pair $(B,C)$ with $(A,B)$ nor $(C,D)$. Otherwise the 2-opt procedure fails. You divide by two because you have $(A,B) = (B,A)$.

Which brings you to the following: $P_{kl} = \dfrac{1}{\delta}$ if 2-opt possible, if not its 0.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.