1507002's blog

By 1507002, history, 6 years ago, In English

Could anyone please tell me how to get the traveled path for Traveling Salesman Problem?

My code is here:

int TSP(int i, int mask){
	if(mask == (1<<n)-1) return w[i][0];
	if(mem[i][mask] != -1) return mem[i][mask];

	int ans = INF;
	for(int j=0; j<n; j++){
		if(w[i][j] == INF) continue;
		if( (mask & (1<<j)) == 0){
			int result = TSP(j, (mask | (1<<j)) ) + w[i][j];
			ans = min(ans, result);
		}
	}
	return mem[i][mask] = ans;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

I think, for each mask, you should save the best next state. Then, it is easy to get the traveled path!