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 中扩展的限制进行更改,如下所示:

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