最短ハミルトン(閉)路問題

・なにそれ
グラフ上の全ての頂点を 1 度ずつ通るパス(サイクル)の最小コストを求める問題
サイクルを求める問題は巡回セールスマン問題とも呼ばれる
NP完全(多項式時間で解けない)で有名

・全部調べたらどうなるのっと
頂点数をNとして、パスならO((N-1)!), サイクルならO(N!)かかる
N<=10くらいまでなら全部試しても高速。C++ならnext_permutaitonを使うと楽

atcoder.jpハミルトン閉路のうち、コストがKであるものを数え上げる。N<=8なので全探索できる

・もっといい方法ないの？
ある。いわゆるbitDP(集合を0と1で扱うDP)を使えば計算量をO(2^N * N^2)まで落とせる
N<=18くらいまでなら競プロの制限時間に間に合うようになる

・なんでbitDPを使うと高速化できるの？
要らない状態を捨ててるから。
結局全部の頂点を通るので通ってきた頂点の順番はどうでもいい。
各頂点を通った/通ってない判定と最後に通った(今いる)頂点だけ分かれば十分。

・お気持ち
dp[S][i]:=通過済みの頂点集合をS(iを含まない)、今いる頂点がiであるときの最小コスト
dp[最後に通る頂点以外の集合][最後に通る頂点]のうち、最小のものが最短ハミルトン路の長さになる。

漸化式
次に通る頂点をi, 直前に通った頂点をjとする
dp[S][i] = min(dp[S - j][j] + cost[j][i])
こんな感じのイメージ……

・例題
atcoder.jpそのまんま巡回セールスマン問題。

atcoder.jp並べる宝石をグラフ、宝石同士の最短距離をコストと考えると最短ハミルトン問題になる

・実装

メモ
・mask >> i AND 1
maskのi番目のビットが立っているかどうか
・mask XOR 1 << j
mask(頂点集合)から最後に通った頂点jのビットを差し引いた(0にした)もの
例: 10110 XOR (1 << 2) = 10010
・1 << k-1 XOR 1 << i
長さkで全部1のビット列からi番目だけを差し引いたもの
・引数
adj:隣接行列グラフ
is_cycle:パスを求めるならfalse, サイクルをならtrueにする
s:始点。-1なら全始点から開始する