コンピュータサイエンスにおいて、ダンシングリンク（DLX ）は、循環的な二重連結リスト（リスト）にノードを追加したり削除したりする手法です。これは、 KnuthのアルゴリズムX（完全被覆問題）[1]などのバックトラッキングアルゴリズムを効率的に実装するのに特に有用です。アルゴリズムXは、再帰的、非決定的、深さ優先、バックトラッキングアルゴリズムであり、完全被覆問題のすべての解を見つけます。よく知られている完全被覆問題には、タイリング、nクイーン問題、数独などがあります。
ドナルド・クヌースによって提案された「ダンシングリンク」という名称は、アルゴリズムの仕組みに由来しています。アルゴリズムの反復により、リンクがパートナーリンクと「ダンス」し、まるで「精巧に振り付けられたダンス」のように見えるからです。クヌースは、このアイデアを1979年に一松宏と野下浩平が考案したと考えていますが[2]、このアイデアを広く普及させたのは彼の論文です。
実装
主なアイデア
DLXのアイデアは、循環的な二重リンクリストのノードにおいて、
x.left.right ← x.right; x.right.left ← x.left;
リストから ノードxを削除しますが、
x.left.right ← x; x.right.left ← x;
x.right と x.left が変更されていないと仮定すると、リスト内のxの位置を復元します。これはリスト内の要素数に関わらず、たとえ要素数が 1 であっても機能します。
クヌースは、アルゴリズムXの単純な実装では、1の探索に膨大な時間がかかることに気づきました。列を選択する際には、行列全体から1を探索する必要がありました。行を選択する際には、列全体から1を探索する必要がありました。行を選択した後は、その行と複数の列から1を探索する必要がありました。この探索時間を計算量O (n)からO(1)に改善するために、クヌースは1のみが格納される 疎行列を実装しました。
行列内の各ノードは常に、左右（同じ行の1）、上下（同じ列の1）、そしてその列のヘッダー（後述）に隣接したノードを指します。行列内の各行と各列は、循環的な二重リンクノードリストで構成されます。
ヘッダ
各列には「列ヘッダー」と呼ばれる特別なノードがあり、これが列リストに含まれ、マトリックス内にまだ存在するすべての列で構成される特別な行 (「制御行」) を形成します。
最後に、各列ヘッダーはオプションでその列内のノード数を追跡することができます。これにより、ノード数が最小の列を見つける計算量は、O ( n × m )ではなくO( n ) となります。ここで、 nは列数、mは行数です。ノード数の少ない列を選択することは、場合によってはパフォーマンスを向上させるヒューリスティックですが、アルゴリズムにとって必須ではありません。
探検
アルゴリズム X では、行と列が定期的にマトリックスから削除され、マトリックスに復元されます。削除は、列とその列の行を選択することで決定されます。選択した列に行がない場合、現在のマトリックスは解くことができず、バックトラックする必要があります。削除が発生すると、選択した行に 1 が含まれるすべての列が削除され、削除された列のいずれかに 1 が含まれるすべての行 (選択した行を含む) も削除されます。列は埋められているために削除され、行は選択した行と競合するために削除されます。1 つの列を削除するには、最初に選択した列のヘッダーを削除します。次に、選択した列に 1 が含まれる行ごとに、行を走査して他の列からそれを削除します (これにより、それらの行にアクセスできなくなり、競合が防止されます)。選択した行に 1 が含まれる列ごとに、この列の削除を繰り返します。この順序により、削除されたノードは 1 回だけ、予測可能な順序で削除されるため、適切にバックトラックできます。結果の行列に列がない場合、それらはすべて埋められ、選択された行が解を形成します。
バックトラッキング
バックトラックを行うには、上記のプロセスを、前述の2番目のアルゴリズムを用いて逆順に実行する必要があります。このアルゴリズムを使用する際の要件の一つは、バックトラックは消去の正確な逆順に実行されなければならないことです。Knuthの論文は、これらの関係とノードの削除と再挿入の仕組みを明確に示しており、この制限を若干緩和しています。
オプションの制約
特定の制約がオプションであるが、一度しか満たすことができない、1被覆問題を解くことも可能です。Dancing Linksは、必ず埋めなければならない主列とオプションの副列によって、これらの問題に対応しています。これにより、アルゴリズムの解のテストが、列のない行列から主列のない行列に変更され、列内の1が最小であるというヒューリスティックが使用されている場合は、主列内でのみチェックする必要があります。Knuthは、nクイーン問題に適用されるオプション制約について説明しています。チェス盤の対角線は、一部の対角線が占有されていない可能性があるため、オプション制約を表します。対角線が占有されている場合、その対角線は一度しか占有できません。
参照
参考文献
- ^ Knuth, Donald E. (2000). 「Dancing links」. Millennial Perspectives in Computer Science . P159. 187. arXiv : cs /0011047 . Bibcode :2000cs.......11047K.
- ^ ヒトツマツ ヒロシ; ノシタ コウヘイ (1979年4月30日). 「バックトラックアルゴリズムの実装手法とその応用」.情報処理レター. 8 (4): 174– 175. doi :10.1016/0020-0190(79)90016-4.（サブスクリプションが必要です）
- ^ 「ダンスリンクを操作するためのオンラインツール」。
外部リンク
- Hadoop MapReduce の例としての分散型 Dancing Links 実装
- C言語で実装されたExact Coverソルバーのフリーソフトウェアです。Algorithm XとDancing Linksを使用しています。数独とロジックグリッドパズルの例題も含まれています。
- DlxLib NuGet パッケージ - DLX を実装する C# クラス ライブラリ
- dlxlib npm パッケージ - DLX を実装する JavaScript ライブラリ
- dancing-links-c++ - DLX を実装する C++ ライブラリ
- go-dancing-links - DLXを実装したGoLangライブラリ
- DLXPy - DLXを実装するPythonライブラリ
- Donald Knuth による CWEB で書かれたダンシングリンクのオリジナル実装。(数独パズルを解くためのフロントエンドも参照してください。)
- ドナルド・クヌースの第24回クリスマス講演会「ダンシング・リンクス」
