Constraints in Search and Knowledge Representation
Constraints and constraint satisfaction are interesting in two ways.
1. Constraints supply a different method of imposing knowledge on a problem.Again, (2) shows the interdependency of knowledge and search. In practice one typically has a set of parameters whose values you are after, and a set of constraints which when applied to a single parameter do not determine it uniquely, but when applied to all the parameters do provide a unique global solution.
2. Constraint propagation enables on to reach a global solution using only local search, with obvious savings in the search space.
The algorithm goes like:
Until a complete solution is found or all paths are deadends
1. Select an unexpanded node of the search graph.
2. Apply the constraint inference rules to the selected node to generate all possible new constraints.
3. If the set of constraints contains a contradiction announce this path is deadend.
4. Else if the set of constraints describes a complete solution announce SUCCESS.
5. Else apply the problem space rules to generatre new partial solutions which are consistent with the latest constraints. Insert these solutions in the search graph.