ハミルトン閉路とは?

任意の頂点から出発してすべての頂点をちょうど 1 回ずつ訪問したのち、最初の頂点に戻ってくることができるようなグラフをハミルトングラフといいます。またそのような順番で頂点を並べた閉路をハミルトン閉路といいます。今回はビットマスクと動的計画法でハミルトン閉路を求めます。

このようなテキストファイルを用意します。1行目が頂点数で、2行目以降がどの頂点がどの頂点へつながっているのかがわかります。これは有向グラフです。「0 1」と「0 1」は別物として扱います。

example.txt

まずテキストファイルのデータを読み出して、どの頂点がどの頂点につながっているのかを調べます。GetAdjacencyMatrixFromFileメソッドは読み取ったテキストファイルから隣接行列を返します。そして得られた隣接行列をHamiltonianCycleクラスに渡して処理をおこないます。

bitmask DP を用いた解法

解を求める方法ですが、訪問順序をすべて列挙して全探索する方法では時間がかかりすぎるので、ここではbitmask DP を用いて解きます。

以下のような DP テーブルを定義します。

DP[S][v] : 頂点集合 S に含まれる頂点をすべて訪問した状態で頂点 v にいるようなパスの個数
(ただし、S は集合の bitmask を整数で表現したものする)

そしてもしv ≠ uである辺 (v, u) が存在し、u は S に含まれていないのであればテーブルを以下のように更新します。

DP[S + 2^u, u] += DP[S, v]

ハイ、意味不明です。鳩もこれを見たとき意味がわかりませんでした。

bitmask による集合の操作とは?

2進法は0と1しかありません。この性質を集合内に要素があるかないかを表わすときに使うのです。

動的計画法で解く

頂点が全部で4つある場合を考えます。

上記のような表をつくります。そしてすべて0で埋めます。わかりやすくするために一番左の列にその行の番号を二進数で表示しています。0001なら頂点番号0のみが訪問済みであるという意味であり、0011なら頂点番号0と1の2つが訪問済みであるという意味です。1111なら4つの頂点すべてが訪問済みであるということになります。

最初は出発点である0番のみが訪問済みであり、現在位置が0番で0番のみが訪問済みのような組み合わせはひとつだけなのでここに1を入れます(A)。この横一列の行でそれ以外の部分は0で埋めます。

もし頂点番号0から1番へ移動可能であるなら頂点番号0と1が訪問済みで現在位置は1番になるので0011の行の赤枠の部分に(A)で入れた値を追加します(B)。また0番から3番に移動可能であれば青枠の部分にも(A)で入れた値を追加します。

頂点番号0から1番へ移動したあと1番から3番に移動可能であればその下の赤枠の部分に(B)で入れた値を追加します(頂点番号0、1、3が訪問済みで最後に訪問したのが3番なので)。

このような処理を上の行から順番におこなっていきます。1111の行の値をすべて足したものがすべての頂点を1回ずつ訪問する方法の数です。ただしハミルトン閉路であるためにはそのあと出発点に戻れなければなりません。最後に訪問した頂点から出発点に戻れる部分だけを足し合わせたものがハミルトン閉路の数となります。

具体的なハミルトン閉路の訪問順を取得するためにはどの頂点から来たのかも記録します。そしてハミルトン閉路であることを確認したら後ろから前へたどっていきます。するとひとつのハミルトン閉路の訪問順序を取得することができます。

あとはこのような処理をするコードを書くだけです。

HamiltonianCycleクラスの定義

HamiltonianCycleクラスを定義します。隣接行列を渡したらハミルトン閉路のひとつを返すメソッドを定義してます。戻り値は訪問すべき順番に並べられた頂点番号のリストです。ハミルトン閉路が存在しない場合は空のリストを返します。