• 5 Local consistency notions
  • 5.6 Directional path consistency
  • 5.7 k-consistency
    • k-CONSISTENCY rule
  • 5.8 Strong k-consistency

5 Local consistency notions

5.6 Directional path consistency

0. Q: 简述“重新排序”时怎么考察directional path consistency.
   A: 在已经指定好变量序列时，对于\(x,y,z\)是子序列，现如果想要考察一个和原始顺序不同的\(\prec\)下的directional path consistency，则对\(\prec\)进行讨论，分三种情况处理。
   举例\(y,z\prec x\)时，只需考察\(C_{y,z}\subset C_{x,y}^T\cdot C_{x,z}\).
   注意这里的做法和directional arc consistency有所不同——在那里是重新构造了CSP \(\mathcal P_\prec\).
   注：定义中，对于\(\prec\)只剪前面，不剪后面，这点定义和directional arc consistency一致。

5.7 k-consistency

0. Q: instantiation的定义域和CSP的定义域是何关系？
   A: instantiation的定义域是CSP变量序列的子序列，而每个分量的值域恰是CSP相应变量的定义域。
1. Q: k-consistent和global consistent, node consistent, arc consistent有何联系？
   A: global consistent等价于存在一个instantiation是k-consistent，其中k是变量总数。
   但global consistent不等价于整个CSP是k-consistent. 比如\(a>0,b>0,a\in\{0\},b\in\{0\}\)显然不存在1-consistent的instantiation，从而vacuously 2-consistent.
   注：可以发现\(k-\)consistent和\(l-\)consistent之间互不蕴涵（\(k\ne l\)）。直观来看，好像\(k\)越大性质越强，但实际上，由于“空虚的真”现象，这也不一定！
   node consistent就是1-consistent.（注：只考虑1元谓词）
   已知node consistent，则arc consistent等价于2-consistent.
2. Q: 已知node consistent，则3-consistent和path consistent有何联系？
   A: 只有二元约束下3-consistent等价于path consistent，否则前者更强，因为后者只考虑二元关系。
3. Q: 构造一个global consistent CSP，是1-consistent，3-consistent，但不是2-consistent.
   把global consistent改成global inconsistent呢？
   A: \(x<y, x<z,x\in \{-1,0,1\},y\in\{0,1\},z\in\{0,1\}\)
   \(x=y,y=z,x\in \{0\},y\in\{1\},z\in\{2\}\)

k-CONSISTENCY rule

0. Q: 如何用变元多的约束构造变元少的约束？如何用多个变元少的约束构造变元多的约束？
   A: projection.
   join.（即多个变元同时满足多个变元少的约束）
1. Q: 说出符号\(\bar C_X\)良定义的关键点。\(\bar C_X\)和\(C_X\)联系如何？
   A: 运算join可交换。
   \(\bar C_X\)比\(C_X\)显然更强。
2. Q: 用\(k=2\)为例解释\(k-\)CONSISTENCY规则\(\frac{C_X}{C_X\cap \prod_X(\bar C_{X,y})}\). 问：k-consistency剪的是几元约束？
   A: 假设node consistent. 则此时，\(\bar C_{X,y}\)就是二元约束，其投影用来剪\(D_X\)（剪一元约束）。
   当\(k=1\)剪1元，否则剪\(k-1\)元。
3. Q: 为什么k-CONSISTENCY的closed under rule和consistent不等价？它相比arc consistent, node consistent, path consistent等有何本质区别？
   A: 其实根源是\(\bar C_{X,y}\)运算。因为\(\bar C_{X,y}\)太强了，包含进了所有子序列的约束。
   提示：回忆：arc consistent等价于closed under the corresponding rule. 而node consistent时，arc consistent等价于2-consistent. 可以看到关键在于node consistent.
   在\(k=2\)，且没有node consistent时，\(\bar C_{X,y}\)太强了，直接包含进了各个一元约束，其投影自然也保留了这些约束。
   于是2-consistent相比arc consistent的规则，因为有那些一元约束所以“额外多剪了”一些定义域（或者说“必须更小心才能不被剪”）。这正是不等价的来由：即使某CSP已经2-consistent了，但因为它没有注意有关一元约束的事情，所以仍然被剪了。
   对于node consistent，因为没有“真子序列”了，自然就不存在此问题。所以1-consistent仍然是和closed under the rule等价。

5.8 Strong k-consistency

0. Q: 已知并非所有定义域都空了，那么strongly k-consistency和global consistency有何关系？
   A: 此时前者推出后者。
   定义域非空和1-consistent得到一个定义域为单元素集的instantiation（起点非空），之后由于没有vacuously consistent了，因此可以归纳地生成一组定义域为所有变量序列的instantiation. 总之，关键就在于保证每一步非空。
   后者不能推出前者（回忆上期提到：local consistency在“剪枝”这一行为上比global consistency苛刻。如果有些定义域有多余的元素，那么global consistency不被破坏但node consistency被破坏）