Constraint Satisfaction
Constraint Satisfaction
复制标题
约束满足
DOI：
10.1007/0-306-48056-5_14
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Mark Wallace
中科院分区：
文献类型：
--
作者：
Eugene C. Freuder;Mark Wallace
在约束网络上定义的约束满足问题（CSP）由一组变量和一组约束组成，每个变量与一个值域相关联。一个解决方案是一个值的分配给每个变量从其域，使所有的约束是萨蒂斯（cid：12）ed。典型的约束满足问题是要确定是否存在一个解决方案，（cid：12）ND一个或所有的解决方案和（cid：12）ND一个最佳的解决方案相对于一个给定的成本函数。约束满足问题的一个例子是众所周知的k -可着色性。问题是如果可能的话，只用k种颜色给给定的图着色，使得任何两个相邻的节点具有不同的颜色。该问题的约束满足公式将图的节点与变量相关联，可能的颜色是它们的域，相邻节点之间的不等式约束是问题的约束。csp的每个约束可以表示为关系，定义在变量的某个子集上，表示它们的法律的值组合。此外，限制
A constraint satisfaction problem (csp) de(cid:12)ned over a constraint network consists of a (cid:12)nite set of variables, each associated with a domain of values, and a set of constraints. A solution is an assignment of a value to each variable from its domain such that all the constraints are satis(cid:12)ed. Typical constraint satisfaction problems are to determine whether a solution exists, to (cid:12)nd one or all solutions and to (cid:12)nd an optimal solution relative to a given cost function. An example of a constraint satisfaction problem is the well known k -colorability. The problem is to color, if possible, a given graph with k colors only, such that any two adjacent nodes have di(cid:11)erent colors. A constraint satisfaction formulation of this problem associates the nodes of the graph with variables, the possible colors are their domains and the inequality constraints between adjacent nodes are the constraints of the problem. Each constraint of a csp may be expressed as a relation, de(cid:12)ned on some subset of variables, denoting their legal combinations of values. As well, constraints