Блог пользователя 1507002

Автор 1507002, история, 6 лет назад, По-английски

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;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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