Knuth's Algorithm XとDancing Linksの解説

Algorithm

Exact Cover Problem

今回解説するKnuth's Algorithm Xは、Exact Cover Problemという問題を解くためのアルゴリズムです。Exact Cover Problemについてはうまい日本語訳が分からない(「敷き詰め問題」とか？)ので英語のまま書いています。

数学で言うと、ある集合Xの部分集合の集合Sが与えられて、そのSの部分集合であるようなS*において、Xに含まれる要素全てがS*の中にひとつだけ含まれるとき、S*はExact Coverであると言います。

ちょっと分かりづらいと思うので具体例を挙げると、まず集合 X = {1, 2, 3, 4, 5} だとします。そして集合 S = {A, B, C, D, E, F} として、A,B,C,D,E,Fは以下のようであるとします。

  • A = {1, 3}
  • B = {1, 4, 5}
  • C = {2, 4}
  • D = {2, 5}
  • E = {3, 4}
  • F = {5}

このとき、S* = {A, C, F} はExact Coverです。なぜなら集合A, C, Fは共通要素を持たず、これらの和集合は {1, 2, 3, 4, 5} でありXと等しいからです。

しかし、S* = {A, C, D} はExact Coverではありません。なぜなら、これらの和集合は {1, 2, 3, 4, 5} になりXと等しくなりますが、CとDでは要素2が共通しているからです。

Knuth's Algorithm X

Knuth's Algorithm Xは、上述のExact Cover Problemを解くためのアルゴリズムです。基本的な考え方はバックトラックによる全探索ですが、それを幾らか改善します。

Algorithm Xでは、Exact Cover Problemの表示を行列で行う必要があります。上で述べた際には、部分集合の中身を書き上げる形で表示していましたが、今度は行列 X[i][j] を「i番目の部分集合に要素jが含まれるかどうか」を表すのに使います。ここでは「含まれる = 1」「含まれない = 0」とします。

上で述べた例を行列にして書き直すと、以下のようになります。

1 2 3 4 5
A 1 0 1 0 0
B 1 0 0 1 1
C 0 1 0 1 0
D 0 1 0 0 1
E 0 0 1 1 0
F 0 0 0 0 1

この行列をXとし、以下の操作を行います。

  • 1. 行列が空である場合は問題が解けたので終了します
  • 2. その列に含まれる1の数が最も少ないような列cを選びます(ただし、1をひとつも含まない列が存在した場合、このアルゴリズムは失敗します)
  • 3. X[r][c] = 1であるようなすべての行rについて以下の操作を行います
    • 4. 行rを解の候補として記録します
    • 5. X[r][j] = 1であるようなすべての列jについて以下の操作を行います
      • X[i][j] = 1であるようなすべての行iについて、行iを行列Xから削除します
      • 列jを行列Xから削除します
    • 6. いろいろな行と列が削除された行列Xについて、もう一度このアルゴリズムを適用します

最後のステップを見ると、このアルゴリズムが再帰的なものであることがわかります。

ただ、この文字列の説明だけでは分かりにくいと思うので、例題をこの方法で実際に解いてみます。以降の説明の中で、文章の先頭に「L-S」(LとSは整数)といった形のものを付記します。これは、現在探索木の深さがLで、ステップSを適用中であることを意味します。

0-1 行列は空でないので適用を続けます。
0-2 1の数が最も少ない列は1,2,3の三つありますが、ここでは左端の1を採用します。

1 2 3 4 5
A 1 0 1 0 0
B 1 0 0 1 1
C 0 1 0 1 0
D 0 1 0 0 1
E 0 0 1 1 0
F 0 0 0 0 1

0-3 列1に1を持つのは行AとBです。最初にAを選択します。
1-4 行Aを解候補として記録します。
1-5 行Aは列1, 3に1を持っています。

1 2 3 4 5
A 1 0 1 0 0
B 1 0 0 1 1
C 0 1 0 1 0
D 0 1 0 0 1
E 0 0 1 1 0
F 0 0 0 0 1

1-5 列1は行A, Bに1を持っており、列3は行A, Eに1を持っています。よって、列1, 3と行A, B, Eは行列から削除されます。

1 2 3 4 5
A 1 0 1 0 0
B 1 0 0 1 1
C 0 1 0 1 0
D 0 1 0 0 1
E 0 0 1 1 0
F 0 0 0 0 1

1-6 列2, 4, 5と行C, D, Fが残りますので、この残った行列にもう一度同じアルゴリズムを適用します。

2 4 5
C 1 1 0
D 1 0 1
F 0 0 1

1-1 行列は空ではないので適用を続けます。
1-2 列4に含まれる1の数が最も少ないので、列4を選択します。

2 4 5
C 1 1 0
D 1 0 1
F 0 0 1

1-3 列4に1を持つのは行Cなので、行Cを選択します。
2-4 行Cを解候補として記録します。
2-5 行Cは列2, 4に1を持っています。

2 4 5
C 1 1 0
D 1 0 1
F 0 0 1

2-5 列2は行C, Dに1を持っており、列4は行Cに1を持っています。よって、列2, 4と行C, Dが削除されます。

2 4 5
C 1 1 0
D 1 0 1
F 0 0 1

2-6 列5と行Fが残ります。

5
F 1

2-1 行列は空ではないので適用を続けます。
2-2 列5に含まれる1の数が最も少ないので列5を選択します。
2-3 列5に1を持つのは行Fなので、行Fを選択します。
3-4 行Fを解候補として選択します。
3-5 行Fは列5に1を持っており、列5は行Fに1を持っているので、列5と行Fが削除されます。

5
F 1

3-1 行列が空になったので解が見つかりました。ここまでに解候補に記録されていたのはA, C, Fなので S* = {A, C, F} という解が存在することがわかります。この探索木はこれ以上深く探索されません。
0-3 次に行Bを選択してみます。
1-4 行Bを解候補として記録します。
1-5 行Bは列1, 4, 5に1を持っています。

1 2 3 4 5
A 1 0 1 0 0
B 1 0 0 1 1
C 0 1 0 1 0
D 0 1 0 0 1
E 0 0 1 1 0
F 0 0 0 0 1

1-5 列1は行A, Bに1を、列4は行B, C, Eに1を、列5は行B, D, Fに1をそれぞれ持っています。よって、列1, 4, 5と行A, B, C, D, E, Fが削除されます。

2 3

1-1 行列は空ではないので適用を続けます。
1-2 1をひとつも含まない列2, 3が存在するので、アルゴリズムは失敗します。

以上のプロセスを経て、この例題には S* = {A, C, F} というひとつの解が存在していたということが分かりました。

Dancing Links

このKnuth's Algorithm Xを実装する際に、行列をただの配列で実現したのでは、行や列の削除、およびバックトラッキングによる削除した行や列の復元が効率よく実装できません。そこで、Dancing Linksというデータ構造を用いることによって、行列を効率よく操作できるよう実装します。

Dancing Linksの基本的なアイデアは双方向循環リストです。行列の要素ひとつをノードひとつに見立て、隣接する上下左右の4要素に対してリンクを張ります。具体例とそのイメージ図を示します。

A B C D
1 1 0 0
0 1 0 1
0 0 1 0

このような構造を使って行列を保持すると、行や列の削除および復元が効率よく行えます。たとえばC言語でノード型を以下のように定義した場合を考えます。

struct dlx_node {
  int value;
  struct dlx_node *left, *right, *up, *down;
};

ここで、struct dlx_node型の変数xがあったとして、このノードを行から削除するには

x.left->right = x.right;
x.right->left = x.left;

という処理を実行します。列から削除する場合はleftをupに、rightをdownに置き換えるだけです。また、削除後にこのノードを復元する場合は

x.left->right = x;
x.right->left = x;

という処理を実行します。列に復元する場合も同様です。このコードはたとえリストの要素数が1でもうまく動作します。

効率化を目指して

行列の保持に、Dancing Linksというデータ構造を使うと削除と復元が効率よく行えることがわかりました。ただAlgorithm Xでは、もうひとつ大事な操作があります。それはある列rに対して、X[r][c] = 1 であるようなcを見つける作業、つまり1の検索です。

1を効率よく検索するためには、疎行列を表す方法と同じように、非ゼロの要素つまり1だけの情報を保持しておくという工夫ができます。上にあげた例において、1だけの情報を保持するようにした場合のイメージ図は以下のようになります。

このように0を無視することで、より高速に処理が可能になります。

実装

http://d.hatena.ne.jp/JAPLJ/20090831/1251709161

Exact Cover Problemを数独に応用する方法についてはまた別に書く予定です。