11

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!

skaffman
  • 398,947
  • 96
  • 818
  • 769
RedShift
  • 275
  • 1
  • 9
  • It is same as generating a factorial from n-1 instead of n. Will this accomplish your objective? – UVM Mar 23 '14 at 04:54
  • @UVM Generating permutations on n-1 cities will not solve my problem. I need to generate a list of permutations on n cities that excludes repeated paths (whether they be cyclic or reversed). – RedShift Mar 23 '14 at 05:09
  • You can try graph theory. Please check this link.http://web.info.uvt.ro/~mmarin/lectures/GTC/c-10.pdf – UVM Mar 23 '14 at 06:11
  • (1-2-3) is the same length than (2-3-1), but also the same length than (3-2-1), right? So actually any combination of three given cities will always have the same length? – sp00m Apr 14 '14 at 10:09

2 Answers2

4

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

Roy van Rijn
  • 840
  • 7
  • 17
0

You can try the zip method, it looks promising:http://web.archive.org/web/20110817142304/http://www.jochen-pleines.de/english/34_nkl.htm.

Micromega
  • 12,486
  • 7
  • 35
  • 72