はじめに
DPを練習している中で、ナップサック問題とかそういうのはできたもののbitDPとか桁DPは敬遠しちゃってました。さすがにいつかは通らないといけない道なのでbitDPから練習することにします！
bitDPとは
bit操作を使って集合を扱うところが特徴的な動的計画法(DP)の一つです。
以下のような漸化式を使って更新していきます。
集合$\{0,1,\dots,n\}$の部分集合Sにおいて
dp[S] = min_{u \in S}{dp[S/\{u\}] + cost[S/\{u\},u]}
集合Sはビット列で扱います。例えば集合$\{0,1,\dots,7\}$においてその部分集合$S=00101001$で表されるときSに含まれるのは$0,3,5$となります。
実際に問題を解いてみる
Traveling Salesman Problemを解いてみました。
重み付きグラフ$G(V,E)$が与えられた時にある頂点から出発し、全ての頂点をちょうど一度づつ通ってから下の頂点に戻るような閉路を求める問題です。
入力:
|V|\ \ |E|\\
s_0\ t_0\ d_0\\
s_1\ t_1\ d_1\\
:\\
s_{|E|−1}\ t_{|E|−1}\ d_{|E|−1}
出力:
最短経路の距離を1行に出力する。条件を満たす経路がない場合は -1 と出力する。
制約:
$2 ≤ |V| ≤ 15$
$0 ≤ d_i ≤ 1,000$
$G$ に多重辺はない
どの頂点から出発しても得られる解は等しいのでここでは頂点0から出発して頂点0に再び戻ってくる場合を考えることにします。
dp[S][v]を頂点0から出発して集合Sに含まれる頂点を一度づつ通り、最終的に頂点$v$へ行くまでの距離の最小値とします。そうすると、全ての頂点を含む集合 $S_{all}$ とした時、dp[ $S_{all}$ ][0]が問の答えになるとわかります。
メモ化再帰を使ったコードは下のようになります。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
const int INF = 1000000000;
int V,E;
int dist[16][16];
int dp[(1<<16)+1][16];
int bitdp(int S,int v){
if(S==0){
if(v==0)return 0;
else return INF;
}
if(dp[S][v]!=0)return dp[S][v];
int mn = INF;
rep(u,V){
if(u==v)continue;
if(!(S & (1<<u)))continue;
mn = min(mn,bitdp(S & ~(1<<u),u)+dist[u][v]);
}
return dp[S][v] = mn;
}
int main() {
cin>>V>>E;
rep(i,16)rep(j,16)dist[i][j]= INF;
rep(i,E){
int s,t,d;cin>>s>>t>>d;
dist[s][t] = d;
}
int ans = bitdp((1<<V)-1,0);
if(ans!=INF)cout<<ans<<endl;
else cout<<-1<<endl;
return 0;
}
上で使っているビット操作は集合Sに頂点uが含まれているか調べる時と集合Sから集合$S/ {u} (u \in S)$を求める時です。
!(S & (1<<u))== true
のときuはSに含まれていません。&は二つのビット列でANDをとります。また、1<<uは1をuだけ左にシフトしています。例えばu = 3のとき1<<uは00001000となります。
S & ~(1<<u)
では集合Sから頂点uを取り除いた集合$S/{u}(u \in S)$を求めています。~はNOT操作でビット列の0,1を反転させます。