CSP Flashcards
what are 3 varieties of constraints?
- unary constraint - single variable constraint e.g. a != green
- binary constraint - pairs of variables are constrained e.g. a != b
- higher order constraint - 3 or more variables constrained
what is the standard search procedure for CSP?
incremental search by
- initial state
- successor function: assign value to unassigned variables that does not conflict with current assignments (no legal assignment = fail)
- goal: all assignments complete
in what aspect is every solution equal in in CSP solving?
every solution in CSP appears at depth n with n variables
what are 4 heuristics in CSP?
CSP heuristics:
1. minimum remaining values heuristic (MRV)
> choose variable with fewest legal values
2. (name?)
> given a variable, choose least constraining value
> rules out fewest values in remaining variables
3. forward checking
> keep track of remaining legal values for unassigned variables
> terminate search whyn any variable has no legal values
4. constraint propagation
> arc consistency/path consistency/k-consistency
arc consistency: when is X-Y arc consistent?
X-Y is consistent iff for every value x of X there is some allowed y
what is an advantage of arc consistency over forward checking?
detects failure earlier
when is a csp said to be locally consistent?
A CSP is said to be locally consistent ifff for particular subsets of the variables it is possible to extend satisying assignments to the variables in the subset to a larger set
when is a CSP called arc consistent?
A CSP is called arc consistent iff a satisfying assignment to one variable can be extended to a satisfying assignment of two variables
does arc concistency constrain the set of solutions?
no, enforcing arc consistency does not change the set of solutions
when is a CSP called path consistent`?
a CSP is called path consistent if any consistent assignment to two variables can be extendet to a third one
> solution invariant as well
how do PC and AC relate to each other?
- PC subsumes AC - if a CSP is PC it is AC as well
2. PC is stronger than AC - there exist a CSP that is AC but not PC
AC removes what?
PC removes what?
AC removes incompatible values from domains
PC removes incompatible pairs of values
when is a CSP called k-consistent?
a CSP is called k-consistent if for each satisfying value assignment to k-1 variables there exists an extension of this assignment to a kth variable such that this extended assignment satisfies all constraints among these k variables
when is a CSP strongly k-consistent?
computation cost?
a CSP is called strongly k-consistent iff it is j-consistent for all j <= k
> computation kosts grow exponentially with k
if a CSP of size n is strongly n-consistent, then…? (3)
- a solution can be constructed in polynomial time
- its constraints are minimal
- it has a solution iff there is no empty constraint
