Print all possible permutations for a TSP problem

How to print all possible city distance permutations of a TSP in Java

Page 1 of 1

6 Replies - 6361 Views - Last Post: 06 September 2010 - 05:16 PM Rate Topic: -----

#1 cordwell  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 19-January 09

Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:06 PM

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


Is This A Good Question/Topic? 0
  • +

Replies To: Print all possible permutations for a TSP problem

#2 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:10 PM

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.
Was This Post Helpful? 0
  • +
  • -

#3 cordwell  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 19-January 09

Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:19 PM

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);
		    					
		    				}
		    			}
		    		}
		    	}
		    }			


Was This Post Helpful? 0
  • +
  • -

#4 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:30 PM

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
Was This Post Helpful? 0
  • +
  • -

#5 cordwell  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 19-January 09

Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:46 PM

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
Was This Post Helpful? 0
  • +
  • -

#6 cordwell  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 19-January 09

Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:58 PM

View Postbcranger, 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.
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10440
  • View blog
  • Posts: 38,668
  • Joined: 27-December 08

Re: Print all possible permutations for a TSP problem

Posted 06 September 2010 - 05:16 PM

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1