algorithm - K 一致但不是强 K 一致

Question

如果对于任何k - 1 个变量的集合以及对这些变量的任何一致分配，始终可以将一致的值分配给任何第 _k_th 个变量，则CSP 是k一致的。一个 CSP 是强 k 一致的，如果它是k一致的并且也是 ( k - 1)-一致的，( k - 2)-一致的，...一直到 1-一致。

从上面的定义中，我不明白 CSP 怎么可能只是k一致但不是强 k一致。

如果 CSP 是k一致的，它是否也必须是k -1 一致的？如果没有，你能举个例子吗？

Answer 1

例如，考虑完成一个部分填充的拉丁方格的问题。

任何只有一个空白单元格的一致网格总是可以完成的。由于只有一个单元格是空白的，因此该单元格所在的行必须恰好缺少一个数字（如果它缺少一个以上的数字，那么根据鸽笼原理，其他数字必须在该行中出现两次，从而导致部分网格不一致）。这同样适用于空白单元格的列，实际上它必须缺少相同的数字（证明留给读者作为练习；提示：计算每个数字的出现次数）。因此，这个缺失的数字可以一致地分配给那个空白单元格。所以 n×n 拉丁方格的 CSP 是 n ²一致的。

另一方面，有很多一致的部分网格（即填充的数字到目前为止没有违反任何规则的网格）在不违反任何规则的情况下无法填充，例如下面的2×2网格不能通过填空将其制成拉丁方格，因为每个空格没有一致的分配：

1 .
. 2

所以这是对两个变量的一致赋值，对第三个变量没有一致的赋值，这意味着 2×2 拉丁方格的 CSP 不是 3-一致的；我们已经证明它是 4 一致的，但现在我们已经证明它不是强4 一致的。