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 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 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 at 23:44
  • $\begingroup$ Thank you so much everyone! So this formula is valid from 3 onwards? Thanks! $\endgroup$
    – stats_noob
    Feb 4 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 at 0:23

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.