On the Satisfiability of Symmetrical Constrained Satisfaction Problems
On the Satisfiability of Symmetrical Constrained Satisfaction Problems
复制标题
对称约束满足问题的可满足性
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
J. Puget
中科院分区：
文献类型：
--
作者：
J. Puget
约束满足问题(CSP)是一类组合问题，通过将弧一致性等一致性方法与回溯搜索相结合，可以有效地求解。然而，这些技术并不适用于对称CSP。事实上，可以表现出不能用一致性技术解决的相当小的CSP。这种对称性问题与现实世界的应用程序有很强的相关性，因为它可以阻止CSP解算器解决现实世界问题的即使是小实例。本文描述了这类问题的一般解决方案。给出了基于约束的库Pecos的理论研究和实验结果。
Constraint satisfaction problems (CSP) are a class of combinatorial problems that can be solved efficiently by combining consistency methods such as arc-consistency together with a backtracking search. However these techniques are not adapted to symmetrical CSP. In fact one can exhibit rather small CSP that cannot be solved with consistency techniques. The relevance of this symmetry problem to real world applications is very strong since it can prevent a CSP solver to solve even small instances of real world problems. This paper describes a general solution for this kind of problems. Both a theoretical study and experimental results using the constraint-based library PECOS are provided.