cse486

  1. is a set of constraints specifying allowable combinations of values for subsets of variables.
    goal test
  2. A state _______ or _______ a black box with no internal structure.
    atomic, or indivisible
  3. defined by variables Xi with values from domain Di–factored representation.
    state:
  4. A constraint satisfaction problem consists of three elements:
    • A set of variables,X=X1, X2, Xn
    • A set of domains for each variable:D=D1, D2, Dn
    • A set of constraints Ct
  5. We call a solution
    consistent assignment
  6. CSP Algorithms: Algorithm can do two things:
    • Search: choose a new variable assignment from many possibilities
    • Inference: constraint propagation, use the constraints to spread the word: reduce the number of values for a variable which will reduce the legal values of other variables etc.
  7. Types of Consistency
    • Node-consistency (unary constraints)
    • Arc-consistency (binary constraints)
    • Path-consistency (n-ary constraints)
  8. A variable Xi is node-consistent if all the values of Domain(Xi) satisfy all unary constraints.
    Node-consistency (unary constraints)
  9. X−> Y is arc-consistent if and only if every value x of X is consistent with some value y of Y.
    Arc-consistency
  10. generalizes arc-consistency from binary to multiple constraints.
    Path-consistency (n-ary constraints):
Author
jonesy
ID
335837
Card Set
cse486
Description
AI
Updated