ここでは、ビットDP（bit DP）について、「プログラミングコンテストチャレンジブック（第2版）」の p173 巡回セールスマンを例に、python3 で実装する方法を、初学者向けに、紹介します。


早速ですが、以下が python3 で実装した場合のコードです。

# 入力
n = 5
INF = float('INF')
d = [[INF, 3, INF, 4, INF],
     [INF, INF, 5, INF, INF],
     [4, INF, INF, 5, INF],
     [INF, INF, INF, INF, 3],
     [7, 6, INF, INF, INF]]

dp = [[0] * n for _ in range(1 << n)] # DPテーブル


def solve(n, d):
    #テーブルを十分大きな値で初期化
    for S in range(1 << n):
        for j in range(n): 
            dp[S][j] = INF
    dp[(1 << n) - 1][0] = 0
    
    #漸化式に従って順に計算
    for S in range((1 << n)-2, -1, -1):
        for v in range(n):
            for u in range(n):
                if not (S >> u & 1):
                    dp[S][v] = min(dp[S][v], dp[S | 1 << u][u] + d[v][u])

    print(dp[0][0])

# 実行部
solve(n, d)


bit 演算について

当たり前の話ではありますが、bit DP という名のとおり、上記コード中では bit 演算が行われています。
そのbit 演算 の部分を詳しくみていきます。

（10 行目）

dp = [[0] * n for _ in range(1 << n)] # DPテーブル

ここでは、「DPテーブル」の作成が行われており、行数の範囲指定に 左シフト 1 << n が使われています。

この 1 << n を n = 5 の時に出力してみると、

n = 5
print(1 << n)
# 32
print(bin(1 << n))
# 0b100000

となり、10進数で32（2進数で 100000） を指定しています。

これは、5つの都市について、訪れたかどうかをあらわす状態の組み合わせが 25 = 32 ことに由来していますね。

ですから、以下のように書くのと同じ意味ですね。

dp = [[0] * n for _ in range(2**5)]


同様の左シフトが、
15、18、および 20行目で使われています。


（24行目）

if not (S >> u & 1):

まずは、(S >> u & 1)　の部分をみてみます。

ここでは、右シフトが使用されています。「S を u（桁）だけ右にずらす」操作です。

この操作により、S に対する u 番目の ビット情報を取り出すことができます。

以下に例をあげてみると、

s = 11
print(bin(s))  #0b1011
u = 1
print(bin(s >> u)) #0b101
u = 2
print(bin(s >> u)) #0b10


2進数 1011 を1つ右にずらせば 101、2つ右にずらせば 10 となっています。

よって、その値が奇数なのか？偶数なのか？をみれば、u 桁目が 0、1のどちらであるか？を確認できることになります。

ちなみに、ここでの u桁目は、右から数え、さらに 0から数える(0 – indexed)ことに注意してください。

さらに、実際の24行目では 偶奇を直接確認するのではなく、& 1 を用いて、右から u 桁目が 0、1 のどちらなのか？を確認しています。

＆ 演算子は、2つの値を比較した場合に、どちらも 1 である場合のみ 1を返します。

これについても例をみると、

s = 11
print(bin(s)) #0b1011
u = 1
print(bin(s >> u)) #0b101
print(bin((s >> u & 1))) #0b1  0101と0001のANDは0001
u = 2
print(bin(s >> u)) #0b10
print(bin((s >> u & 1))) #0b0  0010と0001のANDは0000

となります。

よって、S >> u & 1 は S の右から u 桁目（0 – indexed）は、1であるか？ を確認していることが、わかります。

さらに、not (S >> u & 1) とすることにより、S の右から u 桁目（0 – indexed）は、0 であるか？ の確認になっています。

一応、24行目を偶奇を直接確認する形を、以下に書いてみます。

if (S >> u)%2 == 0:


（25行目）

dp[S][v] = min(dp[S][v], dp[S | 1 << u][u] + d[v][u])

DP テーブルの行を参照する際に、S | 1 << u が使われています。

まずは、 1 << u について考えてみると、

1 を u（桁）だけ左にシフトしたものが作られています。
これにより、2進数で右から u 桁目のみが 1で、その他の桁は 0 であるものができます。
ここでも、0 -indexde であることに注意してください。

さらに、その 1 << u と S の OR（論理和）をとることにより、S の u 桁目を強制的に 1とする操作になっています。


以上が蟻本 P173 「巡回セールスマン問題」で使われている bit演算でした。


お役に立てればうれしいです。