Knuth 的算法 X,用于块大小受限的精确覆盖
Knuth's Algorithm X for exact cover with restricted block sizes
著名的 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 能够根据某些预定义的块大小提供输出。例如,如果 {2, 2}
是块大小集,它将给出输出:{ab, cd}
,如果 {2,1,1}
是块大小集,它将给出输出:{ab, c, d}
,{ac, b, d}
和 {cd, b, a}
。
您可以(可选)从输入列表中删除块大小集中没有大小的所有子集开始。
原始的 Knuth 算法 X 可以用一组块大小(例如 {2, 1, 1})作为使用 bold 中扩展的限制进行更改,如下所示:
- 如果
A
为空且块大小设置为空,问题解决;成功终止。
- 否则选择一列,
c
(确定性)。
- 选择一行,
r
,使得行 r
中的 A[r, c] = 1
和 个 1 在块大小集合中 (不确定)。
- 在部分解决方案中包含
r
- 从块大小集合中删除行
r
中 1 的数量
- 对于每个
j
这样 A[r, j] = 1
,
从矩阵 A
中删除列 j
;
对于每个 i
使得 A[i, j] = 1
,
从矩阵 A
. 中删除行 i
- 对减少的矩阵
A
和 减少的块大小集 . 递归重复此算法
著名的 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 能够根据某些预定义的块大小提供输出。例如,如果 {2, 2}
是块大小集,它将给出输出:{ab, cd}
,如果 {2,1,1}
是块大小集,它将给出输出:{ab, c, d}
,{ac, b, d}
和 {cd, b, a}
。
您可以(可选)从输入列表中删除块大小集中没有大小的所有子集开始。
原始的 Knuth 算法 X 可以用一组块大小(例如 {2, 1, 1})作为使用 bold 中扩展的限制进行更改,如下所示:
- 如果
A
为空且块大小设置为空,问题解决;成功终止。 - 否则选择一列,
c
(确定性)。 - 选择一行,
r
,使得行r
中的A[r, c] = 1
和 个 1 在块大小集合中 (不确定)。 - 在部分解决方案中包含
r
- 从块大小集合中删除行
r
中 1 的数量 - 对于每个
j
这样A[r, j] = 1
, 从矩阵A
中删除列j
; 对于每个i
使得A[i, j] = 1
, 从矩阵A
. 中删除行 - 对减少的矩阵
A
和 减少的块大小集 . 递归重复此算法
i