博士

やあ、ロボ子！今日はAlgorithm Xについて話すのじゃ！

ロボ子

Algorithm X、ですか。初めて聞きます。どんなアルゴリズムなんですか？

博士

Algorithm Xはね、厳密被覆問題を解くためのアルゴリズムなのじゃ。再帰的な非決定性深さ優先バックトラッキングアルゴリズム、ふむ、難しい言葉が並んでるの。

ロボ子

バックトラッキング…ですか。組み合わせ最適化でよく使われる手法ですね。

博士

そうそう！ドナルド・クヌース先生が、Dancing Links（DLX）っていう効率的な実装を実証するために使ったらしいのじゃ。

ロボ子

Dancing Links…なんだか楽しそうな名前ですね。

博士

名前は可愛いけど、中身はすごいぞ！アルゴリズムの手順はこんな感じ。 1. 行列Aに列がない場合、現在の部分解は有効な解であり、正常に終了する。 2. それ以外の場合は、列cを決定的に選択する。 3. A[r, c] = 1となる行rを非決定的に選択する。 4. 行rを部分解に含める。 5. A[r, j] = 1となる各列jについて、A[i, j] = 1となる各行iについて、行列Aから行iと列jを削除する。 6. 縮小された行列Aに対して、このアルゴリズムを再帰的に繰り返す。

ロボ子

なるほど。再帰的に問題を小さくしていくんですね。でも、列を「決定的に選択する」ってどういうことですか？

博士

そこがミソなのじゃ！クヌース先生は、反復回数を減らすために、1の数が最も少ない列を選ぶことを提案したのじゃ。

ロボ子

1の数が少ない列を選ぶ…効率が良さそうですね！

博士

そして、Dancing Linksの出番じゃ！行列の1の要素をDoubly Linked Listsとして実装することで、行と列の削除を高速化するのじゃ。

ロボ子

Doubly Linked Listsですか。削除と挿入がO(1)でできるから、確かに速そうですね。

博士

例えば、こんな例があるぞ。 U = {1, 2, 3, 4, 5, 6, 7} S = {A, B, C, D, E, F} A = {1, 4, 7} B = {1, 4} C = {4, 5, 7} D = {3, 5, 6} E = {2, 3, 6, 7} F = {2, 7} この問題は、Algorithm Xとクヌースのヒューリスティックを使うと、厳密被覆がS = {B, D, F}の一つだけだってわかるのじゃ。

ロボ子

具体例があると分かりやすいです！組み合わせ最適化の問題は、現実世界にもたくさんありますよね。

博士

その通り！例えば、数独を解いたり、鉄道の運行計画を立てたり、様々な問題に応用できるのじゃ！

ロボ子

数独も厳密被覆問題として表現できるんですね。面白いです！

博士

Algorithm XとDancing Linksは、組み合わせ最適化問題を解くための強力な武器になるのじゃ！使いこなせば、キミもスーパーエンジニアじゃ！

ロボ子

ありがとうございます、博士！私もDancing Linksをマスターして、スーパーロボットエンジニアを目指します！

博士

頑張るのじゃ！…そういえば、ロボ子。Dancing Linksって、踊るようにリンクを繋ぎ変えるから、まるで盆踊りみたいじゃな？

ロボ子

…博士、それはちょっと強引すぎます。