正確なカバー問題の有名なアルゴリズムは、Knuth のアルゴリズム X と呼ばれる Donald Knuth によって与えられました。
Input: List of subsets of a Universal sets
Output: All the possible disjoint subset whose union is Universal set
入力が であるとします{ab, ac, cd, c, d, a, b}。事前定義されたブロックサイズに従って出力を与えるように、Knuth のアルゴリズム X を作成することは可能ですか? たとえば、{2, 2}がブロック サイズ セットの場合、出力: 、 がブロック サイズ セットの{ab, cd}場合{2,1,1}、出力: {ab, c, d}、{ac, b, d}およびが得られます{cd, b, a}。
(オプションで) ブロック サイズのセットにサイズがない入力リストからすべてのサブセットを削除することから始めることができます。
元の Knuth のアルゴリズム X は、次のように太字の拡張機能を使用する制限として、ブロック サイズのセット ({2, 1, 1} など) で変更できます。
Aが空で、ブロック サイズのセットが空の場合、問題は解決されています。正常に終了します。cそれ以外の場合は、 (決定論的に)列を選択します。rように、行 を選択します(非決定論的)。A[r, c] = 1rr部分解に含めるrブロック サイズのセットから行内の 1 の数を削除しますjようなそれぞれについて、行列からA[r, j] = 1列を削除します。そのようなそれぞれについて、行列から行を削除します。jAiA[i, j] = 1iAA縮小された行列と縮小されたブロック サイズのセットに対して、このアルゴリズムを再帰的に繰り返します。