-
is a set of constraints specifying allowable combinations of values for subsets of variables.
goal test
-
A state _______ or _______ a black box with no internal structure.
atomic, or indivisible
-
defined by variables Xi with values from domain Di–factored representation.
state:
-
A constraint satisfaction problem consists of three elements:
- A set of variables,X=X1, X2, Xn
- A set of domains for each variable:D=D1, D2, Dn
- A set of constraints Ct
-
We call a solution
consistent assignment
-
CSP Algorithms: Algorithm can do two things:
- Search: choose a new variable assignment from many possibilities
- Inference: constraint propagation, use the constraints to spread the word: reduce the number of values for a variable which will reduce the legal values of other variables etc.
-
Types of Consistency
- Node-consistency (unary constraints)
- Arc-consistency (binary constraints)
- Path-consistency (n-ary constraints)
-
A variable Xi is node-consistent if all the values of Domain(Xi) satisfy all unary constraints.
Node-consistency (unary constraints)
-
X−> Y is arc-consistent if and only if every value x of X is consistent with some value y of Y.
Arc-consistency
-
generalizes arc-consistency from binary to multiple constraints.
Path-consistency (n-ary constraints):
|
|
