The "Travelling Salesman Problem" is a problem where a person has to travel between "n" cities – but choose the itinerary such that:
- Each city is visited only once
- The total distance travelled is minimized
I have heard that if a modern computer were to solve this problem for even 15 cities using "brute force" – it could take years to figure out to calculate the shortest route between these cities! For instance, look at the following link (https://www.sciencedirect.com/topics/earth-and-planetary-sciences/traveling-salesman-problem):
I am interested in learning about "how we can estimate the amount of time required for a computer to solve the Travelling Salesman Problem as the number of cities increases". For a given number of cities, naïve attempt would be to :
- A: Count the total possible number of permutations (n!)
- B: For each permutations, count the number of paths (n)
- C: Multiply each path by the amount of time required to perform a single calculation – i.e. the amount of time required to measure a path (e.g. 1 millisecond)
- Final Answer (i.e. amount of time required to consider all permutations and all paths): A * B * C
My Question: In the above text, it mentions that for "n points", there are "(n-1)!/2" number of paths – it then seems to me that path is multiplied by some "fixed amount of time" that represents the time required per calculation.
I do not know how this formula (n-1)!/2 is derived.
If I had used the logic I identified above, the the total number of paths would be n * n! .
Can someone please show me how this is done?
Thanks!
Best Answer
First of all, $\frac12 (n-1)!$ is counting closed tours that start somewhere, visit all the towns, and return to the start.
A permutation does not give us $n$ of these closed tours. It gives us only one. The permutation $(a_1, a_2, \dots, a_n)$ corresponds to starting at town $a_1$, going to town $a_2$, then to town $a_3$, and so on to $a_n$, then returning to $a_1$.
We divide by $2n$ because each possible closed tour is given by $2n$ different permutations. The permutations $(a_1, a_2, \dots, a_n)$ and $(a_2, a_3, \dots, a_n, a_1)$ and $(a_3, a_4, \dots, a_1, a_2)$ and so on take the same paths, just starting at a different point. (That's the factor of $n$.) The permutations $(a_1, a_2, \dots, a_n)$ and $(a_n, a_{n-1}, \dots, a_1)$ take the same paths, just in reverse order. (That's the factor of $2$.)
So the number of possible closed tours is actually $n!/(2n)$ or $\frac12 (n-1)!$.