当我在阅读关于Knuth的算法X来解决确切的覆盖问题时，我想到了一个边缘情况，我想要澄清一下。
以下是我的假设:
- 给定矩阵a，算法X的"目标是选择行的一个子集，以便数字1在每列中恰好出现一次。"
- 如果矩阵为空，则算法成功终止，那么解就是到该点为止部分解中记录的行的子集。
- 如果有一列为0，则算法终止失败。
参考:http://en.wikipedia.org/wiki/Algorithm_X
考虑矩阵A:[[10][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 10 0]，显然不包括第三列。
我假设算法应该在某个点将矩阵缩减到只有一个0的点，并且不成功地终止。
有人能解释一下吗?
我认为这里的混淆仅仅是在使用术语空矩阵。如果您阅读了Knuth的原始论文(链接到您引用的维基百科文章)，您可以看到他将行和列视为双链表。当他说矩阵是空的，他并不是说它没有条目，他的意思是所有的行和列对象都被删除了。
为了澄清，我将用小写字母标记行，用大写字母标记列，如下所示:
| A | B | C
---------------
a | 1 | 1 | 0
---------------
b | 0 | 1 | 1
该算法声明您确定地选择一列(使用您希望的任何规则)，并且他建议选择具有最少数量的1的列。因此，我们将按照您的建议进行，选择列A。列a中唯一有1的行是行a，因此我们选择行a并将其添加到可能的解{a}中。现在，行a和B在列a和B中有1，所以我们必须删除这些列，以及在这些列中包含1的任何行，即行a和B，就像您所做的那样。得到的矩阵只有一列C，没有行:
| C
-------
这不是一个空矩阵(它还有一列)。但是，列C中没有1，因此，正如算法所指示的那样，我们终止失败。
这可能看起来很奇怪，但如果我们打算使用关联矩阵来解决精确覆盖问题，这是一个非常重要的情况，因为列表示我们希望覆盖的集合X的元素，行表示X的子集。因此，有一些列而没有行的矩阵表示精确覆盖问题，其中可供选择的子集集合是空的(但仍然有点可覆盖)。
如果这个描述给你的实现带来了问题，有一个简单的解决方法:在每个问题中都包含空集。空集(不包含X的任何点)由全为0的行表示。它永远不会被你的算法选择为解决方案的一部分，永远不会与任何其他选择的行冲突，但总是确保矩阵是非空的(至少有一行)，直到所有的列都被删除，这是你真正关心的，因为你需要确保每列都被一些行覆盖。