算法 X 解决精确覆盖 : Fat Matrices

Question

当我阅读 Knuth 的算法 X 以解决精确覆盖问题时，我想到了一个边缘情况，我想对其进行一些说明。

这是我的假设:

1. 给定矩阵 A，算法 X 的“目标是选择行的子集，以便数字 1 在每一列中出现恰好一次。”
2. 如果矩阵为空，则算法成功终止，然后解决方案是在该点之前记录在部分解决方案中的行的子集。
3. 如果有一列为 0，则算法将失败终止。

供引用:http://en.wikipedia.org/wiki/Algorithm_X

考虑矩阵 A:[[1 1 0] [0 1 1]]

我采取的步骤:

给定矩阵 A:

1. Choose a column, c, with the least number of 1's. I choose: column 1

2. Choose a row, r, that contains to a 1 in column c. I choose: row 1

3. Add r to the partial solution.

4. For each column j such that A(r, j) = 1:

       For each row i such that A(i, j) = 1:

           delete row i

       delete column j

5. Matrix A is empty. Algorithm terminates successfully and solution is allegedly: {row 1}.

然而，这显然不是这种情况，因为第 1 行仅包含 [1 1 0]，显然不包括第 3 列。

我会假设该算法应该在某个时候将矩阵减少到只有一个 0 的点并且不成功终止。

有人可以解释一下吗？

Answer 1

我认为这里的混淆仅仅是因为术语空矩阵的使用。如果您阅读 Knuth 的原始论文(链接在您引用的维基百科文章上)，您会发现他将行和列视为双向链表。当他说矩阵为空时，他并不是说它没有条目，他的意思是所有的行和列对象都被删除了。

为了清楚起见，我将用小写字母标记行，用大写字母标记列，如下所示:

   | A | B | C
---------------
 a | 1 | 1 | 0
---------------
 b | 0 | 1 | 1

该算法声明您确定性地选择一个列(使用您希望的任何规则)，他建议选择一个 1 的数量最少的列。因此，我们将按照您的建议进行并选择 A 列。 A 列中唯一带 1 的行是 a 行，因此我们选择 a 行并将其添加到可能的解决方案 { 一个}。现在，a 行在 A 和 B 列中有 1，因此我们必须删除这些列，以及这些列中包含 1 的任何行，即是，行 a 和 b，就像您所做的一样。生成的矩阵只有一列C，没有行:

   | C
-------

这不是一个空矩阵(它还有一列)。但是，C 列中没有 1，因此我们没有成功终止，如算法所示。

这可能看起来很奇怪，但如果我们打算对 Exact Cover Problem 使用关联矩阵，这是一个非常重要的情况。 ，因为列代表我们希望覆盖的集合 X 的元素，行代表 X 的子集。所以一个有一些列但没有行的矩阵代表了确切的覆盖问题，其中可供选择的子集集合是空的(但仍然有要覆盖的点)。

如果此描述导致您的实现出现问题，有一个简单的解决方法:在每个问题中只包含空集。空集(不包含 X 的点)由一行全零表示。它永远不会被您的算法选择为解决方案的一部分，永远不会与任何其他选定的行发生冲突，但始终确保矩阵是非空的(至少有一行)，直到所有列都被删除，这就是您的全部关心，因为您需要确保每一列都被某行覆盖。