ビット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

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です。。。

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が小さい場合のみ。