Results 1 to 5 of 5
Thread: Travelling salesman problem
 11132010, 02:02 PM #1Member
 Join Date
 Nov 2010
 Posts
 2
 Rep Power
 0
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(n1,n) + w(n,1)
Best_S_so_far = ( n, [ 1, 2, 3, ... , n1, 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 :)
 11142010, 12:50 AM #2Member
 Join Date
 Nov 2010
 Posts
 2
 Rep Power
 0
33 views but no help at all :(

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.
 11142010, 01:34 AM #4
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,372
 Blog Entries
 1
 Rep Power
 20
 11142010, 08:12 AM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,525
 Blog Entries
 7
 Rep Power
 20
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.length1; 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 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); }
Joscenosillicaphobia: the fear for an empty beer glass
Similar Threads

travelling between frames
By Stephen Douglas in forum New To JavaReplies: 24Last Post: 07042010, 03:51 PM 
The Travelling Salesman Web Service
By dnaevolutions in forum Java SoftwareReplies: 0Last Post: 02222009, 06:46 PM 
TravelingSalesman 0.7
By JavaBean in forum Java SoftwareReplies: 0Last Post: 11272007, 08:26 PM 
TravelingSalesman 0.6
By JavaBean in forum Java SoftwareReplies: 0Last Post: 11122007, 06:07 PM 
TravelingSalesman 0.5
By JavaBean in forum Java SoftwareReplies: 1Last Post: 11062007, 05:16 AM
Bookmarks