3

著名的精确覆盖问题算法由 Donald Knuth 给出，称为 Knuth's Algorithm 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}。

4

1 回答 1

3

您可以（可选地）从输入列表中删除在块大小集中没有大小的所有子集开始。

原始的 Knuth 算法 X 可以使用一组块大小（例如 {2,1,1}）作为限制使用粗体扩展来更改，如下所示：

  1. 如果A为空且块大小集为空，则问题解决；成功终止。
  2. 否则选择一列，c（确定性地）。
  3. 选择一行，r，使得行中的 1 的数量在A[r, c] = 1块大小的集合中（非确定性地）。r
  4. 包含r在部分解决方案中
  5. r从块大小集中删除行中的 1 数
  6. 对于每个j这样，从矩阵中A[r, j] = 1删除列；对于每个这样，从矩阵中删除行。jAiA[i, j] = 1iA
  7. A在缩减的矩阵和缩减的块大小集上递归地重复此算法。
于 2016-07-12T12:47:25.793 回答