Constraint Satisfaction Problem Flashcards
What is a constraint satisfaction problem?
A set of variables each with a domain of possible values, and a set of constraints that specify allowable combinations of values.
What is cryptarithmetic?
A mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet
What is backtracking search?
Works by assigning values to variables one by one, in different combinations. Whenever a constraint is violated, we go back tot he most recently assigned variable. It is a depth first search kind of algorithm.
What are the properties of backtracking search?
If there are n variables, every solution will occur at depth n.
Variable assignments are commutative.
What is minimum remaining values?
Choose the variable with the fewest legal values.
What is degree heuristic?
A tie-breaker among MRV variables, chooses the variable with the most constraints on remaining variables
What is the least constraining value?
The variable that rules out the fewest values int he remaining variables.
What is forward checking?
Keep track of remaining legal values for unassigned variables and terminate search when any variable has no legal values - prune off that part of the tree and backtrack.
What is constraint propagation?
Simplest form of propogation makes each arc consistent.
What is arc consistency?
Arc consistency detects failure earlier than forward checking. Can be run as a preprocessor after each assignment.
What is variable elimination?
If there is only one variable, return the intersection of its unary constraints. Otherwise
- select a variable X
- Join the constraints in which X appears
- Project R1 onto its variables other than X, forming R2
- Replace all of the constraints in which X appears by R2
- Recursively solve the simplified problem, forming R3
- Return R1 joined with R3
