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!