Summary of Constraint Satisfaction Problems

Constraint Satisfaction Problem

A set of

Xi must take its value from Di.

D have to be a finite set of integers instead of a real-valued domain that would include an infinite number of real-values between two bounds.

  • CSPs are a special kind of problem:

states defined by values of a fixed set of variables

goal test defined by constraints on variable values

  • Backtracking = depth-first search with one variable assigned per node

  • Variable ordering and value selection heuristics help significantly

  • Forward checking prevents assignments that guarantee later failure

  • Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies

  • Iterative min-conflicts is usually effective in practice

Leave a Reply

Your email address will not be published. Required fields are marked *