ビットDPにチャレンジ

今日は、最近よく解いているビットDPについて。

その名のとおりビット演算を用いた動的計画法。

一番分かりやすい例として循環セールスマン問題を考えます。

セールスマンが、営業所を出発し、n個の都市をまわり、営業所に帰ってくる。

n個の都市を最適な順番でまわったとき、どれくらい時間がかかるか？

以下、n個の都市をa,b,c,・・として考えます。

まず、簡単に思いつく解法は全件探索。

a,b,c,d,・・・

a,b,d,c,・・・

a,c,b,d,・・・

・・・・・

とpermutationで探索すると答えはでます。しかし、階乗オーダーとなるため、現実的ではありません。

ここで、

”ある都市から営業所に戻るまでの最短距離は、それまでにどの都市を訪問したかに依存するが、その都市をどの順番で回ったかには依存しない”

ということに気付けばDPが適用できます。

つまり、これまでに辿った経路が

a,b,c,dだろうが、

b,c,a,dだろうが、

c,a,b,dだろうが、

これから先のdから営業所までの最短距離は同じです。

これは、俗に言う「Principle of Optimality」ってやつですね。これでDPが適用できます。

あとは、どの都市を回ったかを覚えておけばいいのですが、これをビットを使って記憶します。

これで、ビットDPの完成です。

例題を解いてみましょう。

http://poj.org/problem?id=2907

view plainprint?

1. typedef pair<int, int>point;  
2. point beeper[12];  
3. int network[12][12];  
4. int dp[12][1<<12];  
5. int n;  
6.   
7. void tsp(int p, int bit) {  
8.    if (bit+1 == 1<<n+1)  
9.        return;  
10.   
11.    REP(i, n+1) {  
12.        if (bit >> i & 1) continue;  
13.        int mask = bit | (1 << i);  
14.        if (!i && mask != (1<<n+1)-1) continue;  
15.   
16.        if (dp[i][mask] > dp[p][bit] + network[p][i]) {  
17.            dp[i][mask] = dp[p][bit] + network[p][i];  
18.            tsp(i, mask);  
19.        }  
20.    }  
21. }  
22.   
23.   
24. int main() {  
25.    int sc, xsize, ysize;  
26.    int x, y;  
27.   
28.    cin >> sc;  
29.    while (sc--) {  
30.        cin >> xsize >> ysize;  
31.        cin >> x >> y;  
32.        beeper[0] = point(--x, --y);  
33.        cin >> n;  
34.   
35.        REP(i, n) {  
36.            cin >> x >> y;  
37.            beeper[i+1] = point(--x, --y);  
38.        }  
39.   
40.        REP(i, n+1)REP(j, n+1)  
41.            network[i][j] = ABS(beeper[i].first - beeper[j].first)  
42.                + ABS(beeper[i].second - beeper[j].second);  
43.   
44.        REP(i,n+1)REP(j, 1<<n+1)  
45.            dp[i][j] = INF;  
46.        dp[0][0] = 0;  
47.        tsp(0, 0);  
48.   
49.        cout << "The shortest path has length " << dp[0][(1<<n+1)-1] << endl;  
50.    }  
51.   
52.    return 0;  
53. }  

typedef pair<int, int>point;
point beeper[12];
int network[12][12];
int dp[12][1<<12];
int n;

void tsp(int p, int bit) {
   if (bit+1 == 1<<n+1)
       return;

   REP(i, n+1) {
       if (bit >> i & 1) continue;
       int mask = bit | (1 << i);
       if (!i && mask != (1<<n+1)-1) continue;

       if (dp[i][mask] > dp[p][bit] + network[p][i]) {
           dp[i][mask] = dp[p][bit] + network[p][i];
           tsp(i, mask);
       }
   }
}


int main() {
   int sc, xsize, ysize;
   int x, y;

   cin >> sc;
   while (sc--) {
       cin >> xsize >> ysize;
       cin >> x >> y;
       beeper[0] = point(--x, --y);
       cin >> n;

       REP(i, n) {
           cin >> x >> y;
           beeper[i+1] = point(--x, --y);
       }

       REP(i, n+1)REP(j, n+1)
           network[i][j] = ABS(beeper[i].first - beeper[j].first)
               + ABS(beeper[i].second - beeper[j].second);

       REP(i,n+1)REP(j, 1<<n+1)
           dp[i][j] = INF;
       dp[0][0] = 0;
       tsp(0, 0);

       cout << "The shortest path has length " << dp[0][(1<<n+1)-1] << endl;
   }

   return 0;
}

tspの部分は、最後に0に戻ってくるような形にしたくて、ちょっとスパゲッティ気味です。。

よく考えると、以下のコードでOKです。。。

view plainprint?

1. void tsp(int p, int bit) {  
2.     REP(i, n+1) {  
3.         if (bit >> i & 1) continue;  
4.         int mask = bit | (1 << i);  
5.         if (dp[i][mask] > dp[p][bit] + network[p][i]) {  
6.             dp[i][mask] = dp[p][bit] + network[p][i];  
7.             tsp(i, mask);  
8.         }  
9.     }  
10. }  

void tsp(int p, int bit) {
    REP(i, n+1) {
        if (bit >> i & 1) continue;
        int mask = bit | (1 << i);
        if (dp[i][mask] > dp[p][bit] + network[p][i]) {
            dp[i][mask] = dp[p][bit] + network[p][i];
            tsp(i, mask);
        }
    }
}

注意）但し、ビットDPでも指数オーダーなので、この方法で解けるのはnが小さい場合のみ。