How Many Possible Routes in the Traveling Salesman Problem?

[O Great One]

The traveling salesman problem is where you have to figure out the shortest route connecting a group of points out of all possible routes. I haven't seen a general math formula to figure out the total number of possible routes given a set of points so I tried to come up with one myself and here's what I got. Let's say that there's four points and you want to know what the total number of possible different routes there are that will connect all four points. Let's assume that the points are numbered 1, 2, 3, and 4. Then these 8 routes are all the same.
12341 23412 34123 41234
14321 21432 32143 43214

The route inbetween the end points can be sequenced in (N-1)! ways and there are N different beginning and endpoints. But, each sequence has N*2 routes that are equivalent so we must divide by that. So this is what we get where N is the number of points:

((N-1)!*N)/(N*2)

We put in 3 points and we get 1 route.
We put in 4 points and we get 3 routes.

The formula seems to be correct and seems to work but I haven't seen it anywhere. Comments?

 

[Gokul43201]

Your expression should simplify to (N-1)!/2 and does look correct. Perhaps the reason this is not found anywhere is that it is trivially simple to see and still has no bearing on the problem other than to show that it is NP complete.

 

[tacman]

Your formula for calculating the number of possible routes in the traveling salesman problem is correct. This is known as the factorial formula and is commonly used in combinatorics to calculate the number of permutations or combinations. It is also used in other mathematical fields such as probability and statistics.

Your formula takes into account the fact that there are multiple ways to arrange the points in a route, but some of these arrangements are equivalent. This is known as overcounting and can lead to incorrect results if not taken into consideration.

It is great that you have tried to come up with a formula yourself and have found it to be correct. However, this formula is well-known and has been used in various applications of the traveling salesman problem. So, you may not have seen it explicitly mentioned as the "traveling salesman formula", but it is a fundamental concept in solving this problem.

Overall, your understanding and application of the formula is accurate and it is good to see that you have a grasp on this important concept in the traveling salesman problem. Keep exploring and learning more about this problem, as it has many real-world applications in fields such as logistics, transportation, and computer science.