Constraint Satisfaction Problems Flashcards
1
Q
4 properties of CSP problems
A
- an action consists of assigning a value to some “object”
- every “object” needs exactly 1 value
- the ordering of actions does not matter
- there are properties involving subsets of the objects that can tell you if you are on the wrong track
2
Q
3 components of CSPs
A
- set of variables {X1, …, Xn}
- set of domains {D1, …, Dn}
- set of constraints
3
Q
constraints
A
specify exactly which combinations of values are allowable
4
Q
task of CSPs
A
for each variable, choose a value from its domain so that all the constraints are satisfied
5
Q
how can constraints be expressed?
A
- informally
- with known relational operators
6
Q
relation
A
a set containing tuples of values
7
Q
constraint relation
A
a set containing tuples of domain values, one from each variable’s domain
8
Q
complete description of a constraint
A
includes variables’ names, and the constraint relationship
