BitMasking DP를 이용한 TSP

 비트마스크 알고리즘 $(Bit Mask)$은 0,1로만 이루어진 이진수를 사용하여 집합과 같은 자료구조를 표현하는 알고리즘이다.  AND연산이나 OR, XOR과 같이 기본연산만 사용하기 때문에 대부분 $O(1)$ 으로 구현되어 시간적으로도 효율적이고, 배열을 사용하지 않기 때문에 메모리 측면에서도 효율적이다. 

 

1. 기본 연산

 비트마스크에 사용되는 대표적인 기본 연산자는 AND$(\space \& \space)$, OR$(\space | \space)$, XOR$(\space \sim \space)$ , NOT$(\space \wedge \space)$, Shift$(\space << \space)$  가 있다. 연산의 결과를 표로 정리하면 다음과 같다.

 

1) AND -> 모두 1일 때만 1

AND	1	0
1	1	0
0	0	0

 

2) OR -> 1이 존재하면 1

OR	1	0
1	1	1
0	1	0

 

3) XOR -> 하나만 1일 때 1

XOR	1	0
1	0	1
0	1	0

 

4) NOT -> 1,0 반전

NOT	1	0
없음	0	1

 

5) Shift 

 a << k : 어떤 정수 a의 비트들을 k칸만큼 밈. Ex) 1<<4 = 16 $(1000_{(2)})$ 

 

2. 집합의 표현

 이진수로 집합을 표현하고, 이런 기본 연산을 이용해서 집합에서 사용되는 연산들을 구현할 수 있다. 예를 들어 집합의 크기가 5라고 하면 00000이 공집합을 의미하고 11111이 모든 원소가포함된 상태를 의미한다. 또 집합이 10110이라면  0번째, 2번째, 3번째 원소만 포함된 집합을 의미한다.

 아래는 집합의 연산들을 기본 연산들을 이용해 구현한 예시이다.

 

출처 : 비트마스크 (BitMask) 알고리즘

 

 

3. TSP

 이제 이를 이용하면 TSP 문제를 $O(N^2\times 2^N)$만에 구현할 수 있다. 

Travelling salesman problem - Wikipedia

 

dynamic programming을 이용하여 풀 것이다. 이때 dp 배열을 다음과 같이 정의하자.

$dp[v][mask] := ($ mask에 포함된 원소들을 모두 순회하고 정점 $v$에 있을 때까지 거쳐간 최소 거리 $)$

여기서  mask는 bitmask 알고리즘을 이용해 구현한 배열을 의미한다. 예를 들어 mask가 35 = 10011_{2}인 경우 0,1,4번째 도시를 순회했다는 의미이다.

 

 먼저 경계조건을 살펴보자. 모든 도시에 대해 자기 자신만 순회하고 자기 자신에있을 때까지 거쳐간 거리는 0일 것이다.  $$dp[v][1<<v] = 0$$ 

 이제 일반적인 $dp[i][mask]$를 살펴보면 정점 $i$를 순회하기 전의 배열은 $bef\_mask = (mask - \{i\})$ 이다. 따라서 bef_mask에 포함된 원소에 대해 $dp[j][bef\_mask] + dist[j][i]$값 중 최솟값이 된다.

$$dp[i][mask] = \min_{j\in bef\_mask}(dp[j][bef\_mask]+dist[j][i])$$

 

이를 이용해 구현해주면 된다.

int TSP(int startCity){
    int dp[1 << N][N];

    for (int mask = 0; mask < (1 << N); mask++){
        for (int i = 0; i < N; i++){
            dp[mask][i] = INF;
        }
    }
    dp[1 << startCity][startCity] = 0; 
    
    for(int mask = 0; mask < (1 << N); mask++){
        for(int c1 = 0; c1 < N; c1++){
            if(!(mask & (1 << c1))) continue;
            for(int c2 = 0; c2 < N; c2++){
                if(!(mask & (1 << c2))) continue; 
                dp[mask][c1] = min(dp[mask][c1], dp[mask^(1<<c1)][c2]+dist[c2][c1]);
            }
        }
    }
    
    int rtv = INF;
    for(int c = 0; c < N; c++){
        rtv = min(rtv, dp[(1 << N) - 1][c] + dist[c][startCity]);
    }
    return rtv;
}