Constraint Networks-英文文献.pdf

1 CONSTRAINT NETWORKS Rina Dechter Information and Computer Science University of California Irvine, CA 92717-3425 1 Intro duction Constraint-based reasoning is a paradigm for formulating knowledge as a set of constraints without sp ecifying the metho d by which these constraints are to b e satised. A variety of techniques have b een develop ed for nding partial or complete solutions for dierent kinds of constraint expressions. These have b een successfully applied to diverse tasks such as design, diagnosis, truth maintenance, scheduling, spatiotemp oral reasoning, logic programming and user interface. Constraint networks are graphical representations used to guide strategies for solving constraint satisfaction pr oblems (CSPs). 1.1 Basic denitions A constraint network (CN) consists of a nite set of variables X = fX ; . . . ; X g, each as- 1 n so ciated with a domain of discrete values, D ; . . . ; D and a set of constraints, fC ; . . . ; C g. 1 n 1 t Each of the constraints is expressed as a relation, dened on some subset of variables, whose tuples are all the simultaneous value assignments to the memb ers of this variable subset that, as far as this