Next: Why are these topics
Up: AI Key Concepts -
Previous: Means-Ends Analysis
- The general problem is to find a solution
that satisfies a set of constraints.
- heuristics used not to estimate the distance to the goal but
to decide what node to expand nest.
- Examples of this technique are design
problem, labelling graphs, robot path planning and cryptarithmetic puzzles (see
last year).
Algorithm:
- Propagate available constraints:
- Open all objects that must be assigned values in a complete solution.
- Repeat until inconsistency or all objects assigned valid valid values:
- select an object and strengthen as much as possible the set of
constraints that apply to object.
- If set of constraints different from previous set then open all objects
that share any of these constraints.
- remove selected object.
- If union of constraints discovered above defines a solution return
solution.
- If union of constraints discovered above defines a contradiction return
failure
3
- Make a guess in order to proceed. Repeat until a solution is found
or all possible solutions exhausted:
- select an object with a no assigned value and try to strengthen its
constraints.
- recursively invoke constraint satisfaction with the current set of
constraints plus the selected strengthening constraint.
dave@cs.cf.ac.uk