アルゴリズム アルゴリズムXでは、完全被覆問題は0と1からなる接続行列 A によって表現される。目標は、各列に数字の1がちょうど1回出現するような行のサブセットを選択することである。
アルゴリズムXは次のように動作します。
行列A に列がない場合、現在の部分解は有効な解である。処理を正常に終了する。 それ以外の場合は、列c を選択します（決定論的に ）。 A r , c rを選択します ( 非決定論的に )。部分解にr 行目を含める。 A r 、 j jについて、 A i , j iについて、 行列A からi 行目を削除します。行列A から列j を削除します。縮小された行列A に対して、このアルゴリズムを再帰的に繰り返します。 r の非決定的な選択は、アルゴリズムが独立したサブアルゴリズムに対して再帰的に実行されることを意味します。各サブアルゴリズムは現在の行列Aを継承しますが、異なる行 r に関してそれを縮小します。列c がすべてゼロの場合、サブアルゴリズムは存在せず、処理は失敗に終了します。
サブアルゴリズムは自然な形で探索木 を形成し、元の問題がルートにあり、レベルkには選択された k 行に対応する各サブアルゴリズムが含まれます。バックトラッキングは、深さ優先で先行順で木を走査するプロセスです。
この手順において列cを 選択するための体系的な規則であれば、どの規則でもすべての解を見つけることができますが、規則によって性能に大きな差があります。反復回数を減らすために、クヌースは列選択アルゴリズムにおいて、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}。この問題は、次の行列で表されます。
クヌースが提案した列選択のためのヒューリスティックを用いたアルゴリズム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} のいずれかに正確に含まれている。 レベル3では選択された行がなくなったため、アルゴリズムはレベル2の次の分岐に進みます。 レベル2では選択された行がなくなったため、アルゴリズムはレベル1の次の分岐に進みます。 レベル1では選択された行がなくなったため、アルゴリズムはレベル0の次の分岐に進みます。 レベル0には分岐が存在しないため、アルゴリズムは終了します。
要約すると、この アルゴリズムは、正確なカバーが1つだけ存在すると判断します。S * = { B , D , F }。
実装 クヌースがアルゴリズム X を記述した主な目的は、ダンシングリンク の有用性を実証することであった。クヌースは、アルゴリズム X がダンシングリンクを使用してコンピュータ上で効率的に実装できることを示し、そのプロセスを「DLX」と呼んだ。DLX は、行列の 1 の 二重リンクリスト として実装された、完全被覆 問題の行列表現を使用する。各 1 要素は、その上、下、左、右の次の 1 にリンクしている。（厳密には、リストが円形であるため、これはトーラス を形成する）。完全被覆問題は疎である傾向があるため、この表現は通常、サイズと必要な処理時間の両方において、はるかに効率的である。DLX は、ダンシングリンクを使用して、行の順列を可能な解としてすばやく選択し、誤った推測を効率的にバックトラック（取り消し）する。[ 1 ]
参考文献 1 2 クヌース、ドナルド (2000)。「踊るリンク」。arXiv : cs /0011047 。↑ Banerjee, Bikramjit; Kraemer, Landon; Lyle, Jeremy (2010-07-04). "マルチエージェント計画認識: 形式化とアルゴリズム" . Proceedings of the AAAI Conference on Artificial Intelligence . 24 (1): 1059– 1064. doi : 10.1609/aaai.v24i1.7746 . ISSN 2374-3468 . 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
外部リンク クヌースの論文- PDFファイル（arXivにも掲載 ： cs/0011047 ） ダンシングリンク最適化について記述したクヌースの論文- Gzip圧縮されたPostScriptファイル。
