9 - Constraint Satisfaction Flashcards
What does a constraint satisfaction problem (CSP) consist of?
X a set of variables
D a set of domains, each is discrete and finite (allowable x values)
C a set of constraints that specify allowable combinations
What does each constraint consist of?
a pair (scope,rel) where
- scope is a tuple of variables
- rel is a relation they can take
Each constraint restricts values
what are the 3 types of assignment?
Consistent = does not violate any constraints
Complete = every variable assigned a value
Partial = some variables assigned a value
How many possible assignments for d values and n variables?
d^n
what are the constraint types
Unary - one var
Binary - two var
Global/Higher-order - n-ary constraints with more than 2 but not necessarily all
- Alldiff = all variables take different values
When is a constraint hypergraph used?
For representing higher order constraints
What is constraint propagation?
The process of using constraints to reduce the number of legal values for a variable then to reduce the values for another and so on
What is node consistency?
A variable is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints
What is arc consistency?
A variable Xi is arc-consistent with Xj if, for every value in the domain Di, there is some variable in Dj that satisfies the constrain on the arc (Xi,Xj)
When is a graph arc consistent?
A constraint graph is arc-consistent if every variable is arc-consistent with every other variable
When is a graph node-consistent?
A constraint graph is node-consistent if every variable in the graph is nodeconsistent
What is the generate and test method?
Exhaustive search of assignment space (set of all assignments of values to its variables)
Each total assignment is generated and checked in turn and those assignments that satisfy are returned
What is back tracking search?
A depth first search that chooses one variable at a time and backtracks when a variable has no legal values left to assign
- Build by searching partial assignments
- Order does not matter
- If during the process a constraint is violated, reject the current partial assignment
Minimum-remaining-values heuristic
Choose the var with the fewest possible legal values.
Most constrained variable
Degree Heuristic
Reduce branching factor by choosing var involved in the largest number of constraints on other unassigned variables
