알고리즘

algospot :: TSP2 Traveling Salesman Problem 2

happilee12 2017. 10. 14. 18:24
반응형

문제 : 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);

반응형