Search on the blog

2010年12月1日水曜日

ビット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の完成です。

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

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

0 件のコメント:

コメントを投稿