C/C++教程

约束式编程学习笔记[5] local consistency (2) 主要是k-consistency

本文主要是介绍约束式编程学习笔记[5] local consistency (2) 主要是k-consistency,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 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

  1. 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

  1. Q: instantiation的定义域和CSP的定义域是何关系?
    A: instantiation的定义域是CSP变量序列的子序列,而每个分量的值域恰是CSP相应变量的定义域。
  2. 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.
  3. Q: 已知node consistent,则3-consistent和path consistent有何联系?
    A: 只有二元约束下3-consistent等价于path consistent,否则前者更强,因为后者只考虑二元关系。
  4. 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

  1. Q: 如何用变元多的约束构造变元少的约束?如何用多个变元少的约束构造变元多的约束?
    A: projection.
    join.(即多个变元同时满足多个变元少的约束)
  2. Q: 说出符号\(\bar C_X\)良定义的关键点。\(\bar C_X\)和\(C_X\)联系如何?
    A: 运算join可交换。
    \(\bar C_X\)比\(C_X\)显然更强。
  3. 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\)元。
  4. 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

  1. Q: 已知并非所有定义域都空了,那么strongly k-consistency和global consistency有何关系?
    A: 此时前者推出后者。
    定义域非空和1-consistent得到一个定义域为单元素集的instantiation(起点非空),之后由于没有vacuously consistent了,因此可以归纳地生成一组定义域为所有变量序列的instantiation. 总之,关键就在于保证每一步非空。
    后者不能推出前者(回忆上期提到:local consistency在“剪枝”这一行为上比global consistency苛刻。如果有些定义域有多余的元素,那么global consistency不被破坏但node consistency被破坏)
这篇关于约束式编程学习笔记[5] local consistency (2) 主要是k-consistency的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!