Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Traveling salesman formula.

  1. Jun 22, 2004 #1
    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:


    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. jcsd
  3. Jun 22, 2004 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook