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.