Variable and value elimination in binary constraint satisfaction via forbidden patterns
Variable and value elimination in binary constraint satisfaction via forbidden patterns
复制标题
DOI：
10.1016/j.jcss.2015.02.001
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
D. Cohen;Martin C. Cooper;Guillaume Escamocher;Stanislav Živný
中科院分区：
文献类型：
--
作者：
D. Cohen;Martin C. Cooper;Guillaume Escamocher;Stanislav Živný
约束满足问题中的变量或值消除可以在预处理或搜索过程中使用，以减小搜索空间的大小。变量消除规则（值消除规则）允许对某些变量（域元素）进行多项式时间识别，这些变量（域元素）的消除不需要引入额外的补偿约束，不会影响实例的可满足性。我们表明，在弧一致CSP实例中，基本上只有四个变量消除规则和三个值消除规则，这些规则是通过禁止一般子实例定义的，称为不可约存在模式。其中一个变量消除规则是已知的破三角属性，而其他三个则是新的。这三个值消除规则都可以看作是邻域替代的严格概括。
Variable or value elimination in a constraint satisfaction problem (CSP) can be used in preprocessing or during search to reduce search space size. A variable elimination rule (value elimination rule) allows the polynomial-time identification of certain variables (domain elements) whose elimination, without the introduction of extra compensatory constraints, does not affect the satisfiability of an instance. We show that there are essentially just four variable elimination rules and three value elimination rules defined by forbidding generic sub-instances, known as irreducible existential patterns, in arc-consistent CSP instances. One of the variable elimination rules is the already-known Broken Triangle Property, whereas the other three are novel. The three value elimination rules can all be seen as strict generalisations of neighbourhood substitution.