algorithm - Knuth 的算法 X，用于 block 大小受限的精确覆盖

Question

exact cover problem的著名算法由 Donald Knuth 给出，称为 Knuth 的算法 X。

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 能够根据某些预定义的 block 大小提供输出。例如，如果 {2, 2} 是 block 大小集，它将给出输出:{ab, cd}，如果 {2,1,1} 是 block 大小集，它会给出输出:{ab, c, d}, {ac, b, d} and {cd , b, a}。

Answer 1

您可以(可选)从输入列表中删除 block 大小集中没有大小的所有子集开始。

原始的 Knuth 算法 X 可以用一组 block 大小(例如 {2, 1, 1})作为使用 bold 扩展的限制进行更改，如下所示:

1. 如果A为空且 block 大小集为空，则问题解决；成功终止。
2. 否则选择一个列，c(确定性地)。
3. 选择一行 r，使得 A[r, c] = 1 和 行 r 中 1 的数量在 block 大小的集合中(不确定)。
4. 在部分解决方案中包含r
5. 从 block 大小集合中删除 r 行中 1 的数量
6. 对于满足 A[r, j] = 1 的每个 j， 从矩阵 A 中删除列 j； 对于满足 A[i, j] = 1 的每个 i， 从矩阵 A 中删除行 i。
7. 在缩减矩阵 A 和缩减 block 大小集 上递归地重复此算法。