初心者のプログラミング日記

プログラミング初心者の日記

プログラミングに関することを書いていきます。

bitDP

今回で動的計画法(DP)の最後です
bitdpを使うと全探索がn<=10ぐらいの所をn<=20ぐらいまで探索できるようになるそうです。
今回は以下の問題を使用します。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja
有名な巡回セールスマン問題(TSP)ですね。

V,E=map(int, input().split())
#でかい値ならOK
INF=10**10
cost = [[INF]*V for _ in range(V)]
for e in range(E):
    s, t, d = map(int,input().split())
    cost[s][t] = d
dp = [[-1] * V for _ in range(1<<V)]
#スタート位置
dp[0][0] = 0

とりあえず、ここまでは一緒ですね。
dpの作り方が今までと違うのでbitdpの考え方を説明します。
まず、bitdoでの集合の表し方は以下の画像のようになります。
f:id:nasubiFX:20201020173640p:plain
画像では分かりやすいように頂点をa,b,c,dとしています。
これを前提に、入力例1を表で表わすと以下のようになります。

集合2進数10進数
{}0b00000
{0}0b00011
{1}0b00102
{0,1}0b00113
{2}0b01004
{0,2}0b01015
{1,2}0b01106
{0,1,2}0b01117
{3}0b10008
{0,3}0b10019
{1,3}0b101010
{0,1,3}0b101111
{2,3}0b110012
{0,2,3}0b110113
{1,2,3}0b111014
{0,1,2,3}0b111115
これで全パターンを網羅できました。

dp = [[-1] * V for _ in range(1<<V)]

pythonではrange(stop)ではstopの値は結果に含まれないので数値を1多くしている。
次の処理を書いていきます。

V,E=map(int, input().split())
INF=10**10
cost = [[INF]*V for _ in range(V)]
for i in range(E):
    s, t, d = map(int,input().split())
    cost[s][t] = d
dp = [[-1] * V for _ in range(1<<V)]

def dfs(S,v):
    if dp[S][v] != -1: # すでに訪れたかどうか
        return dp[S][v]
    if S==(1<<V)-1 and v==0: # 全ての頂点を訪れて頂点0に戻ってきた
        return 0 # もう動く必要はない
 #初期化
    res = INF
    for u in range(V):
        if S>>u & 1 == 0: # 未訪問かどうか
            res = min(res, dfs(S|1<<u, u)+cost[v][u])
    dp[S][v] = res
    return res

ans = dfs(0, 0) # 頂点0からスタートする。ただし頂点0は未訪問とする
if ans == INF:
    print(-1)
else:
    print (ans)

上から解説していきます。

def dfs(S,v):
if dp[S][v] != -1:
        return dp[S][v]
 if S==(1<<V)-1 and v==0:
        return 0 

Sは今いるdpを表し、vは今いる頂点を表します。
1つ目のif文は、今回は-1なら訪問済み、0なら未訪問と扱うので、訪問済みならdpから持ってきます。
2つ目はのif文は全部の頂点を訪れた場合はdp[(1<

 #初期化
    res = INF
    for u in range(V):
        if S>>u & 1 == 0: # 未訪問かどうか
            res = min(res, dfs(S|1<<u, u)+cost[v][u])
    dp[S][v] = res
    return res

初期化は今回は最短経路を求めるので大きい数値なら何でもよい。
今回使うビット演算子の使い方は画像と通りです。

f:id:nasubiFX:20201020195611p:plain
ビット演算子(&,|)

&ビット演算子は両方1なら1をそれ以外は0を返します。
|ビット演算子はどちらかが1なら1を返します。

if S>>u & 1 == 0:

このif分はその頂点をすでに訪れているかをチェックします。
訪れていない場合のみ、その頂点に移動します。
例をいくつか挙げると
S=0の場合対応する集合はdp[0]
dp[0]は2進数で0b0000なのですべての頂点は未訪問になる

S=7の場合対応する集合はdp[7]
dp[7]は2進数で0b0111なので頂点3以外訪れている

S=13の場合対応する集合はdp[13]
dp[7]は2進数で0b1101なので頂点1以外訪れている

S=15の場合対応する集合はdp[15]
dp[15]は2進数で0b1111なのですべての頂点を訪れている

さっきの表のとおりに対応しています。

res = min(res, dfs(S|1<<u, u)+cost[v][u])

ここは次に訪れる可能性がある頂点に行く場合のコストを計算して、一番低いコストを取ります。
例をいくつか挙げると
S=0の場合対応する集合はdp[0]。これを2進数で表すと0b0000なので、次に訪れる可能性がある頂点は0,1,2,3のすべてなので、次の遷移は0b0001(dp[1]),0b0010(dp[2]),0b0100(dp[4]),0b1000(dp[8])のどれかになる。結果は、この中で一番コストが低いところに遷移することになる。

S=13の場合対応する集合はdp[13]。これを2進数で表すと0b1101なので、次に訪れる可能性がある頂点は1のみなので、次の遷移は0b1111(dp[15])となる。

これをどんどん行っていき、最終的にすべての頂点を訪れた結果を返す。

ans = dfs(0, 3)
if ans == INF:
    print(-1)
else:
    print (ans)
print(dp)

今回の場合適当にスタートする頂点を決めても大丈夫(理由はわかりません)なので

ans = dfs(0, 0)#dfs(初期状態、スタートする頂点)
ans = dfs(0, 1)
ans = dfs(0, 2)
ans = dfs(0, 3)

どれでも大丈夫です。ただし、初期状態はdp[0]とすべて未訪問の状態でなければなりません。
頂点を変える場合は以下の所も変更してください

if S==(1<<V)-1 and v==0: # V==0の所をスタートした頂点にする
        return 0

入力例1の場合0-1-2-3-0と行くのが最短経路になるので、2進数で表すと、0b000(dp[0])-0b0010(dp[2])-0b1010(dp[10])-0b1110(dp[14])-0b111(dp[15])の遷移になる。

今回初めてbitを使ったので理解するまで大変でした。
参考サイト
https://kakedashi-engineer.appspot.com/2020/05/21/dpl2a/
https://cinnamo-coder.hatenablog.com/entry/2019/06/23/181751
https://algo-logic.info/bit-dp/#:~:text=%E3%83%93%E3%83%83%E3%83%88DP(bit%20DP)%20%E3%81%A8,(DP)%E3%81%AE%E3%81%93%E3%81%A8%E3%81%A7%E3%81%99%E3%80%82