Using circular permutations to reduce Traveling Salesman complexity

Question

I'm trying out a bunch of different algorithms for finding near-optimal solutions to the Traveling Salesman Problem, and one of the methods is the brute force approach - checking every possible path between n cities, and simply returning the best one. This is an O(n!) algorithm, so naturally it takes a very long time to execute for a large number of cities.

I want to improve the efficiency of my brute force implementation, and one of the things I've noticed is that you don't have to check every single permutation of the cities. For example, if you have cities 1, 2, 3, and 4, the path (1-2-3-4) is the same length as path (2-3-4-1). The same goes for the paths (3-4-1-2) and (4-1-2-3). By exploiting this fact, we should be able to reduce the complexity of the brute force algorithm from O(n!) to O((n-1)!), or even O((n-1)!/2) if we realize that all paths can be reversed without affecting their lengths.

Basically, I'm looking for an algorithm that is capable of generating circular permutations from a set of distinct integers. It would also be great if the algorithm treated "mirrored" permutations as equivalent (e.g. 1-2-3 and 3-2-1 are the same, so only one of them is needed). Does anyone know of a way to accomplish this? A Java implementation would be wonderful, but I'll take anything!

Answer 1

If you always start with the same node (for example '1') you should never run into this problem. Then you can easily add a check for mirrors as well because that is just running from node 0 to N-1 N-2 until you are at zero again.

For example, 1,2,3,4 has the following permutations:

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 

Now if we force 1 as first node, you'll end up with these unique solutions:

1234 1243 1324 1342 1423 1432

Next we can eliminate the 'mirrored' solutions:

normal => reverse => rotated by 1
1234 => 4321 => 1432
1243 => 3421 => 1342
1324 => 4231 => 1423

You'll only need to check:

1234 1243 1324

Update:

The easiest way to generate this sequence is to enumerate all possibilities of 1 ... N-1 where 1 is before 2 (forcing direction) and appending N.

For example for N=4, we first generate all permutations 1 ... N-1:

123 132 213 231 312 321 

Now we filter where 1 is before 2:

123 132 312

And append N (4):

1234 1324 3124

This is probably easier and more efficient to program. This also proves the upper bound needed to brute force TSP is: (N - 1)! / 2