ダンスリンク

コンピュータサイエンスにおいて、ダンシングリンク（DLX ）は、循環的な二重リンクリストからノードを追加および削除するための手法です。これは、完全被覆問題に対するKnuthのアルゴリズムXなどのバックトラッキングアルゴリズムを効率的に実装するのに特に役立ちます。^[1]アルゴリズムXは、完全被覆問題のすべての解を見つける再帰的、非決定的、深さ優先、バックトラッキングアルゴリズムです。よく知られている完全被覆問題には、タイリング、nクイーン問題、数独などがあります。

ドナルド・クヌースが提案した「ダンシングリンク」という名前は、アルゴリズムの繰り返しによってリンクがパートナーリンクと「ダンス」し、「精巧に振り付けられたダンス」に似ていることからこのアルゴリズムが機能するようになったことに由来している。クヌースは、このアイデアを1979年に一松宏と野下浩平が考案したとしているが、^[2]このアイデアを普及させたのは彼の論文である。

この記事の残りの部分では、アルゴリズム X の実装手法の詳細について説明するため、読者はまずアルゴリズム X の記事を読むことを強くお勧めします。

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 であっても機能します。

Knuth は、アルゴリズム X の単純な実装では、1 の検索に膨大な時間がかかることに気づきました。列を選択するときは、マトリックス全体から 1 を検索する必要がありました。行を選択するときは、列全体から 1 を検索する必要がありました。行を選択した後は、その行といくつかの列から 1 を検索する必要がありました。この検索時間を複雑度O(n) から O(1) に改善するために、Knuth は1 のみが格納されるスパース マトリックスを実装しました。

マトリックス内の各ノードは常に、左と右 (同じ行の 1)、上と下 (同じ列の 1) の隣接ノード、およびその列のヘッダー (以下で説明) を指します。マトリックス内の各行と列は、ノードの循環的な二重リンク リストで構成されます。

各列には「列ヘッダー」と呼ばれる特別なノードがあり、これが列リストに含まれ、マトリックス内にまだ存在するすべての列で構成される特別な行 (「制御行」) を形成します。

最後に、各列ヘッダーはオプションでその列のノード数を追跡できるため、ノード数が最小の列を見つける複雑さはO( n ) であり、nは列数、mは行数です。ノード数の少ない列を選択することは、場合によってはパフォーマンスを向上させるヒューリスティックですが、アルゴリズムに必須ではありません。

アルゴリズム X では、行と列が定期的にマトリックスから削除され、マトリックスに復元されます。削除は、列とその列の行を選択することで決定されます。選択した列に行がない場合、現在のマトリックスは解決不可能であり、バックトラックする必要があります。削除が発生すると、選択した行に 1 が含まれるすべての列が削除され、削除された列のいずれかに 1 が含まれるすべての行 (選択した行を含む) も削除されます。列が削除されるのは、列が埋められているためであり、行が削除されるのは、選択した行と競合するためです。1 つの列を削除するには、まず、選択した列のヘッダーを削除します。次に、選択した列に 1 が含まれる各行について、行をトラバースして他の列から削除します (これにより、それらの行にアクセスできなくなり、競合が防止されます)。選択した行に 1 が含まれる各列について、この列の削除を繰り返します。この順序により、削除されたノードは 1 回だけ、予測可能な順序で削除されるため、適切にバックトラックできます。結果の行列に列がない場合、すべての列が埋められ、選択された行がソリューションを形成します。

バックトラックするには、上記のプロセスを、前述の 2 番目のアルゴリズムを使用して逆にする必要があります。このアルゴリズムを使用するための要件の 1 つは、バックトラックを消去の正確な逆として実行する必要があることです。Knuth の論文では、これらの関係とノードの削除と再挿入の仕組みを明確に示し、この制限を少し緩和しています。

特定の制約がオプションであるが、一度しか満たすことができない 1 カバー問題を解くことも可能です。Dancing Links は、必ず埋めなければならないプライマリ列とオプションのセカンダリ列を使用して、これらに対応しています。これにより、アルゴリズムのソリューション テストが、列のない行列からプライマリ列のない行列に変更され、列内の 1 が最小であるというヒューリスティックが使用されている場合は、プライマリ列内でのみチェックする必要があります。Knuth は、nクイーン問題に適用されたオプションの制約について説明しています。チェス盤の対角線は、一部の対角線が占有されていない場合があるため、オプションの制約を表します。対角線が占有されている場合、占有できるのは 1 回だけです。

• 数独を解くアルゴリズム

• 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 ライブラリ
• Donald Knuth による CWEB で書かれたダンシングリンクのオリジナル実装。(数独パズルを解くためのフロントエンドも参照してください。)
• ドナルド・クヌースの第24回クリスマス講演会: ダンシング・リンクス