CSP Algorithms Flashcards
assignment
set of variable-value pairs
how many times do variables appear in assignments?
at most once
partial assignment
some variables unassigned
complete assignment
all variables assigned
consistent assignment
none of the constraints violated
solution to a CSP
a complete and consistent assignment
ways to prevent fruitless search
- don’t try obviously fruitless options
- don’t try options that can be ruled out
Don’t try fruitless ooptions
use the constraints from the problem and the partial assignment in state to check if state is inconsistent
don’t try options that can be ruled out
remove inconsistent domain values from the copy
Techniques for removing inconsistent values
- forward checking
- arc consistency
forward checking
if an assignment violates a constraint remove the assignment option from the domain
arc consistency
remove domain values that don’t have a support in other variables
supported values
a ε DA has support if there is some b ε DB so that (a, b) ε CAB
Minimum remaining values heuristic
choose the variable with the smallest (non-empty) domain first
least constraining value heuristic
choose the value that leaves the most future choices open
- simulate forward checking, use the value that would eliminate fewest values
