Traveling Sales Problem Java Source Code
Public class TSPSolve {
int D[][];
int W[][];
int N, N_POW;
public void computeTSP(int data[][], int n) {
N = n;
N_POW = 1 << n;
W = data;
D = new int [N][N_POW];
for ( int i =0;i<N;i++) {
for(int j=0;j<N_POW;j++) {
D[i][j] = -1;
}
}
//first step : D[i][{}] = W[i][0]
for(int i = 0;i < N ; i ++) {
D[i][0] = W[i][0];
}
int start = 0;
// D[A][{B,C,D}]-> D[start][{1110}]
int cost = tsp( start, N_POW -2);
}
public int tsp(int start, int subset) {
int mask, masked ;
int temp, result=-1;
if(D[start][subset] != -1)
return [start][subset];
for ( int i = 0;i < N ; i++ ) {
mask = (N_POW-1) - (1 << i ) ;
masked = subset & mask;
if(subset != masked) {
// D[A][{BCD}] = min ( W[A][B] + D[B][{C,D}], W[A][C] + D[C][{B,D}] ,W[A][D] + D[D][{B,C}] )
// i=1 , masked = 1100, W[A][B] + D[B][{C,D}] -> W[0][1] + tsp(1,1100) <- recursive call
// D[B][{C,D}] = min (W[B][C] + D[C][{D}], W[B][D] + D[D][{C}]
// W[B][C] + D[C][{D}] -> W[1][2] + tsp(2,1000) <- recursive call
// D[C][{D}] = W[C][D] + D[D][{}] -> W[2][3] + tsp(3,0000) <- first step value will be returned
// W[B][D] + D[D][{C}] -> W[1][3] + tsp(3,0100) <- recursive cal
// D[D][{C}] = W[D][C] + D[C][{}] -> W[3][2] + tsp(2,0000) <- first step value will be returned
// i=2, masked = 1010 W[A][C] + D[C][{B,D}] ...
// i=3, masked = 0110 W[A][D] + D[D][{B,C}] ...
temp = W[start][i] + tsp(i, masked);
if( result == -1 || result > temp) {
result = temp;
}
}
}
D[start][subset] = result;
return D[start][subset];
}
}
최근 덧글