[cordwell]

Help on how to print all possible permutations city/ distance of a TSP problem using Brute Force.
E.g given a file with 3 cities, code should print all possibilities like;
1,2,3 = distance
1,3,2 = distance
2,1,3 = distance
2,3,1 = distance
...
...
...
The code should be able to do this for any file with any number of cities given although it may take time depending with the number of cities. The time taken to run each file should also be recorded and printed

This post has been edited by cordwell: 05 September 2010 - 09:09 PM

[bcranger]

Please post your code as DIC prefers to see a good faith effort on your part before we help you.

As for what you want to do, a String permutation generator should accomplish what you need...look into permutations if you want.

[cordwell]

This is what I have so far, whic is specifically for 4 cities. How do I make it possible for any number of cities

int a, b, c, d;
		    double dist1 = 0;
		    double dist2 = 0;
		    double dist3 = 0;
		    double dist4 = 0;			    
		    double totalDist = 0;
		    
		    System.out.println("\nCity Path " + " \tTotal Distance ");
		    for(a=0; a<cityCount; a++){
		    	
		    	for(b=0; b<cityCount; b++){
		    		
		    		for(c=0; c<cityCount; c++){
		    			
		    			for(d=0; d<cityCount; d++){
		    				
		    				if(!(a==b || a==c || a==d || b==c || b==d || c==d)){
		    					dist1 = Math.sqrt(((xpoints.get(B)/> - xpoints.get(a)) * (xpoints.get(B)/> - xpoints.get(a))) + ((ypoints.get(B)/> - ypoints.get(a)) * (ypoints.get(B)/> - ypoints.get(a))));
		    					dist2 = Math.sqrt(((xpoints.get(c) - xpoints.get(B)/>) * (xpoints.get(c) - xpoints.get(B)/>)) + ((ypoints.get(c) - ypoints.get(B)/>) * (ypoints.get(c) - ypoints.get(B)/>)));
		    					dist3 = Math.sqrt(((xpoints.get(d) - xpoints.get(c)) * (xpoints.get(d) - xpoints.get(c))) + ((ypoints.get(d) - ypoints.get(c)) * (ypoints.get(d) - ypoints.get(c))));
		    					dist4 = Math.sqrt(((xpoints.get(a) - xpoints.get(d)) * (xpoints.get(a) - xpoints.get(d))) + ((ypoints.get(a) - ypoints.get(d)) * (ypoints.get(a) - ypoints.get(d))));
		    					totalDist = dist1 + dist2 + dist3 + dist4;			    					
		    					System.out.println((a+1) + ", " + (b+1) + ", " + (c+1) + ", " + (d+1) + ", " + (a+1) + " \t" + totalDist);
		    					
		    				}
		    			}
		    		}
		    	}
		    }			

[bcranger]

Put all city numbers into a single string and generate all possible permutations. THen split each string and calculate the distances you need.

Here's a permutation generator found on google:
http://www.merriampark.com/perm.htm

[cordwell]

The input is a file. Code should read file, extract all the cities and their x, y coordinates. every city has a city number, like this: This a 5 city file.

NAME: concorde5
TYPE: TSP
COMMENT: Generated by CCutil_writetsplib
COMMENT: Write called for by Concorde GUI
DIMENSION: 5
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 31.045752 75.527426
2 42.565359 77.004219
3 64.705882 76.160338
4 50.735294 33.333333
5 53.104575 90.717300

[cordwell]

bcranger, on 05 September 2010 - 08:30 PM, said:

Put all city numbers into a single string and generate all possible permutations. THen split each string and calculate the distances you need.

Here's a permutation generator found on google:
http://www.merriampark.com/perm.htm

I tried to use this template code but it did not work for me. I could not be able to calculate the respective distances of the cities. Since a total distance of each path posibility has to be recorded and printed too.

[macosxnerd101]

There are a bunch of permutation snippets in the Java Snippets section like KYA's and mostyfriedman's. There are also a few File I/O Tutorials if you need a starting point for reading in the File. The way I would model this is to use the java.awt.geom.Point2D.Double class to represent each city. And as Point2D has a distance() method which accepts another Point2D object, you just have to permute the indices for the array or List<Point2D.Double>.

So for example, if one permutation is: 23451, get elem 2 and elem 3 and find the distance, then elems 3 and 4, etc. until you get through elems 5 and 1. With a sum variable, it should be pretty straight-forward to get total distance.