Results 1 to 5 of 5
  1. #1
    sofcne is offline Member
    Join Date
    Nov 2010
    Posts
    2
    Rep Power
    0

    Default Travelling salesman problem

    hi all;
    i'm new in the java world and im seeking some help plz
    i wanna implement an exhaustive algorithm of TSP(travelling salesman problem) in java
    in this algorithme the travelling salesman have to visit a set of cities only once and he have to return to the first city he left from;
    its an exhaustive algorithme bcuz in it we try everypossible path and then see the path with the lowest cost but im not gonna change the first city im leavin ill fix the city that ill start from it wont change
    here is the algorithm :
    N = {1, 2, ... , n} is the nodes
    S = (k, [i1, i2, ... ,ik], w) is an ordered set which includes a partial path (ordered list of k integers) and the sum of its edge weights w
    w = w(1,2) + w(2,3) + w(3,4) + ... + w(n-1,n) + w(n,1)
    Best_S_so_far = ( n, [ 1, 2, 3, ... , n-1, n ], w )
    S = ( 1, [ 1 ], 0 )
    Search( S, Best_S_so_far )
    print Best_S_so_far

    procedure Search( S, Best_S_so_far )

    let ( k, [ i1, i2, ... , ik ], w ) = S
    let ( n, [ i1B, i2B, ... , inB ], wB ) = Best_S_so_far
    if k = n then
    new_w = w + w(ik,i1)
    if new_w < wB then
    Best_S_so_far = ( k, [ i1, i2, ... , ik ], new_w )
    end if
    else
    for all j not in [ i1, i2, ... , ik ]
    new_w = w + w(ik,j)
    New_S = ( k+1, [ i1, i2, ... , ik, j ], new_w )
    Search( New_S, Best_S_so_far )
    end for
    endif
    return
    end


    hope you will help me out in programin this in java :)

  2. #2
    sofcne is offline Member
    Join Date
    Nov 2010
    Posts
    2
    Rep Power
    0

    Default

    33 views but no help at all :(

  3. #3
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    You haven't asked an answerable question anywhere. Where do you state clearly what your problems are? what's not working right? If you want help, you're going to have to help us help you.

  4. #4
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by sofcne View Post
    33 views but no help at all :(
    Even it more than 33 you never found a solution to your question, because you are not specifically ask your question. And also you haven't show your effort over here. No one wants to write applications for you.

  5. #5
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,518
    Blog Entries
    7
    Rep Power
    20

    Default

    Let i1 i2 i3 ... in be the index numbers of the cities in the tour; those index numbers are a permutation of the numbers 1 2 3 ... n. You want to check all permutations for an optimal tour. If n is large (say 100) your algorithm will run forever but it will terminate once. If you define a lexicographical ordering of the number i1 i2 i3 ... in you can find a next permutation given a current one as follows:

    Java Code:
    	public static void swap(int[] s, int i, int j) {
    		int t= s[i];
    		s[i]= s[j]; s[j]= t;
    	}
    	
    	public static int[] permute(int[] t) {
    		
    		int i, j;
    		
    		for (i= t.length-1; --i >= 0;)
    			 if (t[i] < t[i+1])
    				 break;
    		
    		if (i < 0) return null;
    		
    		for (j= t.length; --j > i;)
    			if (t[i] < t[j])
    				break;
    		
    		swap(t, i, j);
    		
    		for (j= t.length; ++i < --j;)
    			swap(t, i, j);
    		
    		return t;
    	}
    The method permute( ... ) permutes an array of index values and returns the next permutation in lexicographical order (if any). If there is no such permutation anymore it returns null.

    The following method shows how it works:

    Java Code:
    	public static void main(String[] args) {
    		int[] a= { 1, 2, 3, 4 };
    		do {
    			System.out.println(Arrays.toString(a));
    		}
    		while ((a= permute(a)) != null);
    	}
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. travelling between frames
    By Stephen Douglas in forum New To Java
    Replies: 24
    Last Post: 07-04-2010, 03:51 PM
  2. The Travelling Salesman Web Service
    By dnaevolutions in forum Java Software
    Replies: 0
    Last Post: 02-22-2009, 06:46 PM
  3. Traveling-Salesman 0.7
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 11-27-2007, 08:26 PM
  4. Traveling-Salesman 0.6
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 11-12-2007, 06:07 PM
  5. Traveling-Salesman 0.5
    By JavaBean in forum Java Software
    Replies: 1
    Last Post: 11-06-2007, 05:16 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •