Constraint Satisfaction Tutorial
<p>Feb 26, 2009 8:42 PM
 
CSP's  constr satifac problems.
 </p>
<h1>What is a constraint satisfaction problem?</h1>
<p>As can be inferred from the name, this set of problems deal with constraints. These constraints are no different from the ones that inhabit our real-world. There are<b> constraints all around us</b>, such as <b>temporal constraints (managing work and home life), or tangible constraints (making sure we don't go over budget),</b>
 
<b>(solving problems when resources are limited)</b>
 
 
Examples:  Oper Research:  scheduling  (eg scheduling shifts in the ER a la Robert Fan
bioinformatics  DNA sequencing      solving a crossword puzzle;  jigsaw puzzle;  solving protein 3d structure
circuit layout in ee
 
The formal definition of a CSP involves variables and their domains, and constraints. Suppose we have a set of variables, X<sub>1</sub>, X<sub>2</sub>, ..., X<sub>n</sub>, all with domains D<sub>1</sub>, D<sub>2</sub>, ..., D<sub>n</sub> such that all variables X<sub>i</sub> have a value in their respective domain D<sub>i</sub>. There is also a set of constraints, C<sub>1</sub>, C<sub>2</sub>, ..., C<sub>m</sub>, such that a constraint C<sub>i</sub> restricts (imposes a constraint on) the possible values in the domain of some subset of the variables. <b>A solution to a CSP is an assignment of every variable some value in its domain such that every constraint is satisfied. </b>Therefore, each assignment (a state change or step in a search) of a value to a <b>variable must be consistent: it must not violate any of the constraints.</b>
As in any AI search problem, there can be multiple solutions (or none). To address this, a CSP may have a preference of one solution over another using some preference constraints (as opposed to all absolute constraints), want all solutions, <b>or the optimal solution, given by an objective function</b>.
   (all constraints satisfied...  yields maximum  expected utility)
 
Example  N-Queens problem;  eg  8 queens on an 8*8 chessboard.
 
Heuristic Search
 
 
 
 </p>