AIMA: Constraint Satisfaction Problems
Flashcards
CSP representation and components
What sort of representation do CSPs use in comparison to the atomic representation used by search algorithms?
A factored representation.
What is the domain of a variable in a CSP?
The set of the variables it can take on.
What are the constraints in a CSP?
Expressions that limit what values a variable can take on.
What are inference techniques in CSPs?
Using constraints to rule out certain variable assignments.
Variable and value ordering heuristics
What is the minimum-remaining-values heuristic?
Choosing variables with the smallest domain to assign values to next.
What is the degree heuristic for CSPs?
Choosing variables involved in the largest number of constraints to assign values to next.
What is the least-constraining-value heuristic?
Choosing values for variables that have the smallest affect on constraining other variables.
Backtracking and learning
What is conflict-directed backjumping?
Backtracking to the source of conflicts rather than the last modification made.
What is constraint learning in CSPs?
Recording conflicts made as a CSP is searched for solutions to avoid future conflicts.
Tree-structured CSPs
Why is it a good idea to turn CSPs into trees?
Because trees can be solved in polynomial time.
What are the two ways of transforming a normal graph CSP into a tree?
- Cutset conditioning
- Tree decomposition