ハミルトン閉路とは？
任意の頂点から出発してすべての頂点をちょうど 1 回ずつ訪問したのち、最初の頂点に戻ってくることができるようなグラフをハミルトングラフといいます。またそのような順番で頂点を並べた閉路をハミルトン閉路といいます。今回はビットマスクと動的計画法でハミルトン閉路を求めます。
このようなテキストファイルを用意します。1行目が頂点数で、2行目以降がどの頂点がどの頂点へつながっているのかがわかります。これは有向グラフです。「0 1」と「0 1」は別物として扱います。
example.txt
|
1 2 3 4 5 6 7 8 9 |
4 0 2 1 3 2 0 3 1 0 1 1 2 2 3 3 0 |
まずテキストファイルのデータを読み出して、どの頂点がどの頂点につながっているのかを調べます。GetAdjacencyMatrixFromFileメソッドは読み取ったテキストファイルから隣接行列を返します。そして得られた隣接行列をHamiltonianCycleクラスに渡して処理をおこないます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
using System; using System.Collections; using System.Collections.Generic; using System.Linq; public class Program { static bool[,] GetAdjacencyMatrixFromFile(string filePath) { System.IO.StreamReader sr = new System.IO.StreamReader(filePath); string str = sr.ReadToEnd(); sr.Close(); str = str.Replace("\r", ""); string[] arr = str.Split(new string[] { "\n" }, StringSplitOptions.RemoveEmptyEntries); int vertexCount = int.Parse(arr[0]); // 1行目は頂点の数 bool[,] adjacencyMatrix = new bool[vertexCount, vertexCount]; for (int i = 1; i < arr.Length; i++) { int[] sg = arr[i].Split().Select(_ => int.Parse(_)).ToArray(); adjacencyMatrix[sg[0], sg[1]] = true; } return adjacencyMatrix; } static void Main() { bool[,] matrix = GetAdjacencyMatrixFromFile(ファイルのパス); HamiltonianCycle hamilton = new HamiltonianCycle(); List<int> path = hamilton.GetPath(matrix); Console.WriteLine(string.Join(" ", path)); } } |
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しかありません。この性質を集合内に要素があるかないかを表わすときに使うのです。
|
1 2 3 4 5 6 7 8 9 |
D C B A 0001 // A のみが存在する 0010 // B のみが存在する 0011 // A と B が存在する 0100 // C のみが存在する 0101 // A と C が存在する 0110 0111 1000 |
動的計画法で解く
頂点が全部で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クラスを定義します。隣接行列を渡したらハミルトン閉路のひとつを返すメソッドを定義してます。戻り値は訪問すべき順番に並べられた頂点番号のリストです。ハミルトン閉路が存在しない場合は空のリストを返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
public class HamiltonianCycle { public List<int> GetPath(bool[,] adjacencyMatrix) { // DPテーブルの行数は（2 の頂点数乗 + 1）、列数は頂点数 int vertexCount = adjacencyMatrix.GetLength(0); long rowMax = (1 << vertexCount) - 1; int[,] dp = new int[rowMax + 1, vertexCount]; dp[1 << 0, 0] = 1; // 出発点である0番を訪問済みにする // どこから来たのかを記録するDPテーブル int[,] dpFrom = new int[rowMax + 1, vertexCount]; for (int row = 0; row < rowMax + 1; row++) { for (int col = 0; col < vertexCount; col++) dpFrom[row, col] = -1; } dpFrom[1 << 0, 0] = 0; // DPテーブルを上の行から埋めていく for (long bits = 0; bits <= rowMax; bits++) { for (int col = 0; col < vertexCount; col++) { if (dp[bits, col] == 0) continue; for (int goal = 0; goal < vertexCount; goal++) { // 同じ頂点間の移動はしない if (col == goal) continue; // 移動できない頂点間の移動はしない if (!adjacencyMatrix[col, goal]) continue; // 訪問済みの頂点への移動はしない if ((bits >> goal & 1) == 1) continue; // 訪問先の情報を書き込む long newBits = bits | (1 << goal); dp[newBits, goal] += dp[bits, col]; dpFrom[newBits, goal] = col; } } } // DPテーブルのrowMax行で0以外の値をもつ列の番号が最後に訪問する頂点番号である // 最後に訪問した頂点と0がつながっているのであれば、それはハミルトン閉路である int lastIndex = -1; // ハミルトン閉路で最後に訪問した頂点の番号（初期値は不適切な数としての -1） int count = 0; for (int col = 0; col < vertexCount; col++) { if (dp[rowMax, col] > 0 && adjacencyMatrix[col, 0]) { count = dp[rowMax, col]; lastIndex = col; } } // count ハミルトン閉路は何通りあるか？ // Console.WriteLine(count); List<int> path = new List<int>(); if (lastIndex != -1) { long bits = rowMax; while (true) { path.Add(lastIndex); if (lastIndex == 0) break; int lastIndex2 = dpFrom[bits, lastIndex]; bits ^= 1 << lastIndex; lastIndex = lastIndex2; } path.Reverse(); path.Add(0); // 閉路の頂点番号は0ではじまり0で終わるようにする return path; } else return new List<int>(); // 閉路が存在しない場合は空のリストを返す } } |
