algospot :: TSP2 Traveling Salesman Problem 2

문제 : https://algospot.com/judge/problem/read/TSP2

알고리즘 문제 해결 전략 1권 p. 319

주어진 문제와 책에 주어진 코드가 조금 다름

[알고리즘 STEP.1]

지금 있는 도시와 지금까지 방문한 도시를 바탕으로, 남은 도시를 모두 방문하는 거리 합의 최소값을 재귀적으로 구해야 한다.

*double cache[MAX][1<<MAX]; // 2^MAX

cache[i][j]는 현재 도시가 i 지금까지 방문한 도시가 j일 때, 남은 도시를 모두 방문하는 거리 합의 최소를 저장한다.

1<<n 은 2^n을 반환한다. 즉 2진수로 n번째자리가 1인 수 1000...00를 반환하는 것이다. 

도시가 총 n개 있을 때 각 도시를 방문하거나 하지 않은 경우의 수는 2^n개가 된다.

총 도시의 수가 15개라면, 방문한 도시는 1, 방문하지 않은 도시는 0으로 갖는 이를 15자리 이진수로 표현할 수 있게 된다.

*double play2(int here, int visited)

현재 도시 here과 지금까지 방문한 도시를 표현한 정수 visited에 대해 남은 도시를 모두 방문하는 거리 최소합을 반환한다.

각 도시를 다음번에 방문한다고 가정 했을 때   

FOR(next, n)

만약 next 도시가 이미 방문한 도시라면 건너뛰고

if(visited & (1<<next)) continue; 

// visited의 k번째 수가 1이고 1<<next의 k번째 수가 1이면 1을 반환한다. 즉 이미 방문한 도시라면 k번째 자리가 1이 된다.

// 방문하지 않은 도시라면 모든 자릿수가 0이 되므로 0을 반환

그렇지 않다면 here도시와 next도시 사이의 거리 + next도시에서 나머지 도시들을 다 가는 거리의 최소값을 구하고 

double cand = distBtwCity[here][next]+play2(next, visited+(1<<next));

그 값이 현재의 cache[here][visited] 보다 작으면  값을 업데이트한다.

double play2(int here, int visited){ // cout << "here: " << here <<" visited : " << bitset<32>(visited) <<endl; if(visited == (1<<n)-1) return 0; double &ret = cache[here][visited]; if(ret >0) return ret; ret = INF; FOR(next, n){ if(visited & (1<<next)) continue; double cand = distBtwCity[here][next]+play2(next, visited+(1<<next)); ret = min(ret, cand); } return ret; }

[최종코드]

0부터 n번도시 중 어느 것에서 먼저 시작할지 모든 경우를 시도해 보아야 한다.

//https://algospot.com/judge/problem/read/TSP1 //https://algospot.com/judge/problem/read/TSP2 #include <iostream> #include <cstring> #include <limits> #include <bitset> #define FOR(i, ed) for(int i = 0 ; i < ed; i++) #define INF std::numeric_limits<double>::infinity(); #define MAX 20 using namespace std; // input int tc, n; double distBtwCity[MAX][MAX]; //distances between city i and j // for algorithm double cache[MAX][1<<MAX]; // 2^(MAX-1)인가? void inputData(){ FOR(i, n) FOR(j, n) cin >> distBtwCity[i][j]; } double play2(int here, int visited){ // cout << "here: " << here <<" visited : " << bitset<32>(visited) <<endl; if(visited == (1<<n)-1) return 0; double &ret = cache[here][visited]; if(ret >0) return ret; ret = INF; FOR(next, n){ if(visited & (1<<next)) continue; double cand = distBtwCity[here][next]+play2(next, visited+(1<<next)); ret = min(ret, cand); } return ret; } int main(){ // freopen("input.txt", "r", stdin); cin >> tc; while(tc--){ memset(cache, -1, sizeof(cache)); cin >> n; inputData(); double rslt = INF; FOR(start, n){ rslt = min(rslt, play2(start, 1<<start)); } cout.precision(10); cout << rslt << endl; } }

[내가 헤맨 부분]

- 그냥 비트연산자는 어려움... 코드 이해하기 너무 어려웠다...

- double형에서 +무한대 값 : #define INF std::numeric_limits<double>::infinity();

- 2진수 출력 bitset<32>(target)

- 소수 n번째 자리까지 출력 cout.precision(n);