K一致但不强K一致



CSP是k-一致的,如果对于k-1变量的任何集合以及对这些变量的任何一致赋值,总是可以将一致值赋给任何_k_th变量。如果CSP是k-一致的,并且也是(k-1(-一致的、(k-2(-一致、。。。一直到1一致。

根据上面的定义,我不明白CSP是如何做到k-一致的,而不是strongk的-一致的。

如果CSP是k-一致的,那么它不一定也必须是k1-一致吗?如果没有,你能举个例子吗?

例如,考虑完成部分填充的拉丁正方形的问题。

任何只有一个空白单元格的一致网格总是可以完成的。由于只有一个单元格为空,因此该单元格所在的行必须恰好缺少一个数字(如果它缺少多个数字,则根据鸽子洞原理,其他一些数字必须在该行中出现两次,从而使局部网格不一致(。同样的情况也适用于空白单元格的列,事实上,它必须缺少相同的数字(校对留给读者练习;提示:计算每个数字的出现次数(。因此,这个缺失的数字可以一致地分配给那个空白单元格。因此n个拉丁正方形的CSP是n2-一致的。

另一方面,有很多一致的部分网格(即,到目前为止,其填充的数字没有违反任何规则的网格(,在不违反任何规则情况下无法填充,例如,以下2×2网格不能通过填充空格制成拉丁正方形,因为每个空格都没有一致的赋值:

1 .
. 2

因此,这是一组对两个变量的一致赋值,而对第三个变量没有一致赋值,这意味着2×2拉丁平方的CSP不是3-一致的;我们已经证明了它是4-一致的,但现在我们已经证明它不是4-一致的。

相关内容

  • 没有找到相关文章

最新更新