# Traveling salesman formula.

1. Jun 22, 2004

### 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?

2. Jun 22, 2004

### Gokul43201

Staff Emeritus
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.