クヌースのアルゴリズムX

アルゴリズムXは、正確な被覆問題を解くアルゴリズムです。これは、ドナルド・クヌースがダンシングリンク技法を使用するDLXと呼ばれる効率的な実装を示すために使用した、単純な再帰的、非決定的、深さ優先、バックトラッキングアルゴリズムです。^{[1] [2]}

正確なカバー問題は、アルゴリズム X では0 と 1 で構成される接続行列 Aによって表されます。目標は、各列に数字 1 が 1 回だけ出現するように行のサブセットを選択することです。

アルゴリズム X は次のように動作します。

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を削除します。

   行列Aから列jを削除します。

6. このアルゴリズムを縮小行列A上で再帰的に繰り返します。

r の非決定論的な選択は、アルゴリズムが独立したサブアルゴリズムを再帰的に実行することを意味します。各サブアルゴリズムは現在の行列Aを継承しますが、異なる行rに関してそれを縮小します。列cが完全にゼロの場合、サブアルゴリズムは存在せず、プロセスは失敗して終了します。

サブアルゴリズムは自然な方法で検索ツリーを形成し、元の問題がルートにあり、レベルkにはk 個の選択された行に対応する各サブアルゴリズムが含まれます。バックトラッキングは、深さ優先でツリーを事前順序でトラバースするプロセスです。

この手順で列c を選択するための体系的なルールはどれもすべてのソリューションを見つけますが、一部のルールは他のルールよりもはるかにうまく機能します。反復回数を減らすために、Knuth は列選択アルゴリズムで 1 の数が最も少ない列を選択することを提案しています。

たとえば、宇宙U = {1, 2, 3, 4, 5, 6, 7} と集合S = { A , B , C , D , E , F } の集合によって指定される正確な被覆問題を考えてみます。

• 1 , 4, 7 です。
• 1 = {1, 4};
• 4, 5, 7 の整数
• 3, 5, 6 の整数部分
• E = {2, 3, 6, 7}; および
• 2,7である。

この問題は次の行列で表されます。

列を選択するための Knuth が提案したヒューリスティックを使用したアルゴリズム X は、この問題を次のように解決します。

レベル0

ステップ 1 - 行列は空ではないので、アルゴリズムは続行されます。

ステップ 2 - どの列でも 1 の最小数は 2 です。列 1 は 1 が 2 個ある最初の列なので、(決定論的に) 選択されます。

ステップ 3 - 行Aと行B の列 1 にはそれぞれ 1 があるため、選択されます (非決定論的)。

アルゴリズムはレベル 1 の最初のブランチに移動します...

レベル1: 行Aを選択

ステップ 4 - 行Aが部分的なソリューションに含まれます。

ステップ 5 - 行A の列 1、4、7 に 1 があります。

列 1 には行AとBに 1 があり、列 4 には行A、B、Cに 1 があり、列 7 には行A、C、E、Fに 1 があります。したがって、行A、B、C、E、Fを削除し、列 1、4、7 を削除します。

行Dが残り、列 2、3、5、6 が残ります。

ステップ 1 - 行列は空ではないので、アルゴリズムは続行されます。

ステップ 2 - どの列でも 1 の最小数は 0 であり、列 2 は 1 が 0 個である最初の列です。

したがって、アルゴリズムのこのブランチは失敗して終了します。

アルゴリズムはレベル 1 で次のブランチに移動します...

レベル1: 行Bを選択

ステップ 4 - 行Bが部分的なソリューションに含まれます。

行B の列 1 と 4 に 1 があります。

列 1 には行AとBに 1 があり、列 4 には行A、B、Cに 1 があります。したがって、行A、B、Cを削除し、列 1 と 4 を削除します。

行D、E、Fが残り、列 2、3、5、6、7 が残ります。

ステップ 1 - 行列は空ではないので、アルゴリズムは続行されます。

ステップ 2 - どの列でも 1 の最小数は 1 です。列 5 は 1 が 1 つある最初の列であるため、選択されます (決定論的に)。

ステップ 3 - 行D の列 5 に 1 があるため、選択されます (非決定論的)。

アルゴリズムはレベル 2 の最初のブランチに移動します...

レベル2: 行Dを選択

ステップ 4 - 行Dが部分的なソリューションに含まれます。

ステップ 5 - 行D の列 3、5、6 に 1 があります。

列 3 の行DとEには 1 があり、列 5 の行Dには 1 があり、列 6 の行DとEには 1 があります。したがって、行DとEは削除され、列 3、5、および 6 は削除されます。

行Fが残り、列 2 と 7 が残ります。

ステップ 1 - 行列は空ではないので、アルゴリズムは続行されます。

ステップ 2 - どの列でも 1 の最小数は 1 です。列 2 は 1 が 1 つある最初の列であるため、選択されます (決定論的に)。

行F の列 2 には 1 があるため、選択されます (非決定的)。

アルゴリズムはレベル 3 の最初のブランチに移動します...

レベル3: 行Fを選択

ステップ 4 - 行Fが部分的なソリューションに含まれます。

行F の列 2 と 7 に 1 があります。

列 2 の行Fには 1 があり、列 7 の行Fには 1 があります。したがって、行Fを削除し、列 2 と列 7 を削除します。

行も列も残りません:

ステップ 1 - マトリックスは空なので、アルゴリズムのこのブランチは正常に終了します。

行B、D、Fが選択されているため (手順 4)、このブランチの最終的なソリューションは次のようになります。

言い換えると、部分集合 { B , D , F } は完全被覆です。なぜなら、すべての要素は集合B = {1, 4}、D = {3, 5, 6}、またはF = {2, 7} のいずれか 1 つに含まれるからです。

レベル 3 では選択された行がなくなったため、アルゴリズムはレベル 2 の次のブランチに移動します。

レベル 2 には選択された行がもうないので、アルゴリズムはレベル 1 の次のブランチに移動します。

レベル 1 には選択された行がもうないので、アルゴリズムはレベル 0 の次のブランチに移動します。

レベル 0 には分岐がないため、アルゴリズムは終了します。

要約すると、アルゴリズムは、正確なカバーが 1 つだけあることを決定します: S ^* = { B、D、F }。

クヌースがアルゴリズム X を説明した主な目的は、ダンシング リンクの有用性を実証することだった。クヌースは、ダンシング リンクを使用してアルゴリズム X をコンピュータ上で効率的に実装できることを、クヌースが「DLX」と呼ぶプロセスで示した。DLX は、正確な被覆問題の行列表現を使用して、行列の 1 の二重リンク リストとして実装されている。つまり、各 1 要素には、その上、下、左、右にある次の 1 へのリンクがある (技術的には、リストは循環的であるため、トーラスが形成される)。正確な被覆問題はスパースになる傾向があるため、この表現は通常、サイズと必要な処理時間の両方においてはるかに効率的である。次に、DLX はダンシング リンクを使用して、可能な解として行の順列をすばやく選択し、誤った推測を効率的にバックトラック (元に戻す) する。^[1]

• 正確なカバー
• ダンスリンク

• Knuth, Donald E. (2000)、「Dancing links」、Davies, Jim、Roscoe, Bill、Woodcock, Jim (編)、『Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare』、Palgrave、pp. 187–214、arXiv : cs/0011047、Bibcode :2000cs.......11047K、ISBN 978-0-333-92230-9。

• Knuth の論文 - PDF ファイル ( arXiv :cs/0011047 でも参照)
• Dancing Links の最適化について説明した Knuth の論文 - Gzip 圧縮された PostScript ファイル。