クヌースのアルゴリズム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 } の集合によって指定される正確な被覆問題を考えます。

  • A = {1, 4, 7};
  • B = {1, 4};
  • C = {4, 5, 7};
  • 3, 5, 6 の整数部分
  • E = {2, 3, 6, 7}; および
  • F = {2, 7}。

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

1 2 3 4 5 6 7
あ 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1

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

レベル0

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

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

1 2 3 4 5 6 7
あ 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1

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

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

レベル1: 行Aを選択
ステップ 4 - 行Aは部分的なソリューションに含まれます。
ステップ 5 - 行A の列 1、4、7 に 1 があります。
1 2 3 4 5 6 7
あ 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
列 1 には行AとBに 1 があり、列 4 には行A、B、Cに 1 があり、列 7 には行A、C、E、Fに 1 があります。したがって、行A、B、C、E、Fを削除し、列 1、4、7 を削除します。
1 2 3 4 5 6 7
あ 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
行Dが残り、列 2、3、5、6 が残ります。
2 3 5 6
D 0 1 1 1
ステップ 1 - 行列は空でないので、アルゴリズムは続行されます。
ステップ 2 - どの列でも 1 の最小数は 0 であり、列 2 は 1 が 0 個である最初の列です。
2 3 5 6
D 0 1 1 1
したがって、アルゴリズムのこのブランチは失敗して終了します。
アルゴリズムはレベル 1 で次のブランチに移動します...
レベル1: 行Bを選択
ステップ 4 - 行Bが部分的なソリューションに含まれます。
行B の列1 と 4 に 1 があります。
1 2 3 4 5 6 7
あ 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
列1には行AとBに1があり、列4には行A、B、Cに1があります。したがって、行A、B、Cを削除し、列1と列4を削除します。
1 2 3 4 5 6 7
あ 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
行D、E、Fが残り、列 2、3、5、6、7 が残ります。
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
ステップ 1 - 行列は空でないので、アルゴリズムは続行されます。
ステップ2 — どの列でも1の最小数は1です。5列目は1が1つある最初の列なので、（決定論的に）選択されます。
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
ステップ 3 - 行D の列 5 に 1 があるため、選択されます (非決定論的)。
アルゴリズムはレベル 2 の最初のブランチに移動します...
レベル2: D行を選択
ステップ 4 - 行Dは部分的なソリューションに含まれます。
ステップ 5 - 行D の列 3、5、6 に 1 があります。
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
列3の行Dと行Eには1があり、列5の行Dには1があり、列6の行Dと行Eには1があります。したがって、行Dと行Eを削除し、列3、列5、列6を削除します。
2 3 5 6 7
D 0 1 1 1 0
E 1 1 0 1 1
F 1 0 0 0 1
行Fが残り、列 2 と 7 が残ります。
2 7
F 1 1
ステップ 1 - 行列は空でないので、アルゴリズムは続行されます。
ステップ2：どの列でも1の最小数は1です。列2は1が1つある最初の列なので、（決定論的に）選択されます。
2 7
F 1 1
行F の列 2 には 1 があるため、選択されます (非決定論的)。
アルゴリズムはレベル 3 の最初のブランチに移動します...
レベル3: 行Fを選択
ステップ 4 - 行Fが部分的なソリューションに含まれます。
行F の列2 と 7 に 1 があります。
2 7
F 1 1
列2の行Fには1があり、列7の行Fには1があります。したがって、行Fを削除し、列2と列7を削除します。
2 7
F 1 1
行も列も残りません:
 
ステップ 1 - マトリックスは空なので、アルゴリズムのこのブランチは正常に終了します。
行B、D、Fが選択されているため (手順 4)、このブランチの最終的なソリューションは次のようになります。
1 2 3 4 5 6 7
B 1 0 0 1 0 0 0
D 0 0 1 0 1 1 0
F 0 1 0 0 0 0 1
言い換えれば、サブコレクション { 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]

参照

参考文献

  1. ^ ab Knuth, Donald (2000). 「Dancing links」. arXiv : cs/0011047 .
  2. ^ Banerjee, Bikramjit; Kraemer, Landon; Lyle, Jeremy (2010-07-04). 「マルチエージェントプラン認識：形式化とアルゴリズム」. AAAI人工知能会議論文集. 24 (1): 1059– 1064. doi : 10.1609/aaai.v24i1.7746 . ISSN  2374-3468.
  • ドナルド・E・クヌース（2000年）「ダンシング・リンクス」、ジム・デイヴィス、ビル・ロスコー、ジム・ウッドコック（編）、ミレニアル世代の視点によるコンピュータサイエンス：トニー・ホーア卿を記念した1999年オックスフォード・マイクロソフトシンポジウム議事録、パルグレイブ、 187～ 214頁 、 arXiv：cs/0011047、書誌コード：2000cs.......11047K、ISBN 978-0-333-92230-9。
  • Knuthの論文 - PDFファイル（arXiv : cs/0011047でも参照）
  • Dancing Links の最適化について説明した Knuth の論文 - Gzip 圧縮された PostScript ファイル。
「https://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&oldid=1267470602」より取得