A Logical Approach to Constraint Satisfaction
A Logical Approach to Constraint Satisfaction
复制标题
约束满意度的逻辑方法
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Moshe Y. Vardi
中科院分区：
文献类型：
--
作者：
Phokion G. Kolaitis;Moshe Y. Vardi
自20世纪70年代初以来，人工智能（AI）的研究人员研究了一类组合问题，这些问题后来被称为约束满足问题（CSP）。这类问题的输入包括一组变量、这些变量的一组可能值以及变量之间的一组约束；问题是确定是否对满足给定约束的变量赋值。约束满足的研究在人工智能中占有突出的地位，因为在不同领域出现的许多问题都可以自然地建模为约束满足问题；这些领域包括布尔可满足性、时间推理、信念维护、机器视觉和调度（参见[Dec92a，Kum92,Mes89, Tsa93]）。一般来说，约束满足是一个np完全问题。因此，人工智能领域的研究人员既追求约束满足问题的启发式，也追求通过对输入施加各种限制而获得的可处理案例（参见[MF93，Dec92a,DM94,Fro97,PJ97]）。
Since the early 1970s, researchers in artificial intelligence (AI) have investigated a class of combinatorial problems that became known as constraint-satisfaction problems (CSP). The input to such a problem consists of a set of variables, a set of possible values for the variables, and a set of constraints between the variables; the question is to determine whether there is an assignment of values to the variables that satisfies the given constraints. The study of constraint satisfaction occupies a prominent place in artificial intelligence, because many problems that arise in different areas can be modelled as constraint-satisfaction problems in a natural way; these areas include Boolean satisfiability, temporal reasoning, belief maintenance, machine vision, and scheduling (cf. [Dec92a,Kum92,Mes89, Tsa93]). In its full generality, constraint satisfaction is an NP-complete problem. For this reason, researchers in artificial intelligence have pursued both heuristics for constraint-satisfaction problems and tractable cases obtained by imposing various restrictions on the input (cf. [MF93,Dec92a,DM94,Fro97,PJ97]).