2
$\begingroup$

I'm just learning about the travelling salesman problem, and I've been playing around with it. I'm not sure if what I've found is just a special case or not. My professor says the search space size is $n!$, where $n$ is the number of cities.

Suppose we have a table with cities $A,B,C,D$ on each axis, and the elements represent the distances between cities:

\begin{array}{|c|c|c|c|} \hline & A & B & C & D \\ \hline A&0 & 2& 3&4\\ \hline B& 2 & 0& 10&5\\ \hline C& 3 &10 &0 &15\\ \hline D& 4 & 5& 15&0\\ \hline \end{array}

From this, I can generate various permutations of possible tours, and their lengths: $$A \to B \to C \to D \to A : 31$$ $$A \to B \to D \to C \to A : 25$$ $$A \to C \to B \to D \to A : 22$$ $$A \to C \to D \to B \to A : 25$$ $$A \to D \to B \to C \to A : 22$$ $$A \to D \to C \to B \to A : 31$$

Now, it seems to me that each of these permutations is cyclical. In this way, $B \to C \to D \to A \to B : 31 $ and $A \to B \to C \to D \to A : 31$ are equivalent, for example.

So in fact, it doesn't matter which city I choose initially, because the resulting shortest tour will be equivalent to one of the tours above.

And clearly, there are $3!$ of these tours, or $(n-1)!$ of them. So why isn't the search space size $(n-1)!$ instead of $n!$? Maybe there is a problem with my understanding of what search space size is, I'm not sure.

$\endgroup$
3
$\begingroup$

The search space has size $(n-1)!$. You can see this in many ways, for example:

  1. Each tour corresponds to $n$ different permutations, depending on the starting point.
  2. If we start describing the tour at some point $P$ fixed ahead of time, then the tour is given (injectively) by an arbtirary permutation of the remaining $n-1$ points.

The reason that sometimes $n!$ is used is that $n!$ is shorter, and the difference between $n!$ and $(n-1)!$ is not always important.

$\endgroup$
4
  • $\begingroup$ Hi, thanks for the answer. Are you able to expand slightly on when and why the difference between $n!$ and $(n-1)!$ is not always important? The factor of $n$ between them feels quite significant to me $\endgroup$ – Data Jun 30 '19 at 16:08
  • $\begingroup$ Sometimes it suffices to know that $n!$ is super-exponential, or more accurately $\exp \Theta(n\log n)$. The exact value of the hidden constant doesn’t matter. At other times the difference between $n!$ and $(n-1)!$ is more significant. $\endgroup$ – Yuval Filmus Jun 30 '19 at 16:12
  • $\begingroup$ @YuvalFilmus, is it true though that the cycle costs are the same no matter what the starting point is? $\endgroup$ – heretoinfinity Mar 7 at 18:32
  • $\begingroup$ $a+b+c=b+c+a=c+a+b$. $\endgroup$ – Yuval Filmus Mar 7 at 18:35

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.