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 :)

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.

Quote:

---

Originally Posted by sofcne

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.

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:

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:

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