Counting the Number of Paths in the "Travelling Salesman Problem"

Question

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!

Answer 1

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)!$.