0
$\begingroup$

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):

enter image description here

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!

$\endgroup$
1
  • $\begingroup$ Each permutation represents exactly one path. $\endgroup$
    – aschepler
    Feb 3, 2022 at 18:56

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This fails for $n=1,2$. :) $\endgroup$
    – user
    Feb 3, 2022 at 23:34
  • $\begingroup$ Yes, there are not $\frac12$ closed tours when $n=1$ :) The reason it fails is that when $n=1$ or $n=2$, it is not meaningful to "reverse" a closed tour. $\endgroup$ Feb 3, 2022 at 23:44
  • $\begingroup$ Thank you so much everyone! So this formula is valid from 3 onwards? Thanks! $\endgroup$
    – stats_noob
    Feb 4, 2022 at 5:36
  • $\begingroup$ @ Misha Lavrov : Can you please take a look at this question if you have time? math.stackexchange.com/questions/4416714/… Thank you so much! $\endgroup$
    – stats_noob
    Mar 31, 2022 at 0:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .