Constraint Satisfaction Search Algorithm

Constraint Satisfaction Search

A constraint search does not refer to any specific search algorithm but to a layer of complexity added to existing algorithms that limit the possible solution set. Heuristic and acquired knowledge can be combined to produce the desired result a constraint satisfaction problem is a special kind of search problem in which states are defined by the values of a set of variables and the goal state specifies a set of constraints that the value must obey. There are many problems in AI in which the goal state is not specified in the problem and it requires to be discovered according to some specific constraint. Examples of some constraint satisfaction search include design problem, labeling graphs, robot path planning and cryptarithmatic problem etc.

that subset. The search space of CSPS is often exponential. Therefore a number of different approaches to the problem have been proposed to reduce the search space and find a feasible solution in a reasonable time based on the search space exploring and variable selection heuristics different algorithms and can be developed for a CSP problem. The algorithms can be divided into two major categories such as complete and incomplete algorithm.

Complete algorithms seek any solution or solutions of a CSP or they try to prove that no solution into the categories like constraint propagation techniques which tries to eliminate values that are consistent with some constraints and systematic search techniques. Which explores systematically the whole search space. But on the other hand incomplete search methods do not explore the whole search space. They search the space either non-systematically or in a systematic manner, but with a limit on some resource.

They may not provide a solution but their computational time is reasonably reduced. They cannot be applied to find all solutions or to prove that no solution exists. Let us look an algorithm to solve a constraint satisfaction problem.

Algorithm:

1)    Open all objects that must be assigned values in a complete solution.

2)    Repeat until all objects assigned valid values.

3)    Select an object and strengthen as much as possible. The set of constraints that apply to object.

4)    If set of constraints is different from previous set then open all objects that share any of these constraints. Remove selected objects.

5)    If union of constraints discovered above defines a solution, return solution.

6)    If union of constraints discovered above defines a contradiction, return failure.

7)    Make a guess in order to proceed. Repeat until a solution is found.

8)    Select an object with a number assigned value and try strengthen its constraints.