Constraints Satisfaction Problem in AI

Constraints Satisfaction

  • One type of problem-solving strategy that works for many problems is constraint satisfaction.

  • In many AI challenges, the objective is not stated clearly in the problem description.
  • These categories include problems like crypto-arithmetic puzzles, design tasks requiring the creation of designs, and material where constraint satisfaction is relevant.
  • Formally, a set of variables {V1, V2,,,,,,,, Vn} and a set of constraints {C1, C2,,,,,,, Cn} characterize a constraint satisfaction.

Thus, Constraint Satisfaction is a Two Steps Process:

  • Firstly, Constraint satisfaction is discovered and propagated throughout the system.
  • If there is no solution, and a search begins, a guess is made and added to the constraint.

Constraint Satisfaction Problem in AI  Algorithm

1. Propagate available constraints 

  • Open each object that needs a value supplied for the solution to be complete. 
  • Continue until an inconsistency is found or until all objects have valid values assigned to them.
  • Choose an item and make the constraints that are applied to it stronger. 
  • Open all objects that share any of the restrictions if the collection of constraints differs from the previous set. 
  • Take the chosen thing out.

2. Return the solution if the set of restrictions that you found above identifies a solution.

3. Return failure if the combination of the criteria found above defines a contradiction.

4. Assume to move forward. Continue until a solution is discovered or every option has been considered:

  • constraint
    • Choose an item and attempt to make its constraints stronger. It has an allocated number.
    • Invoke constraint satisfaction recursively using the chosen strengthening constraint in addition to the current set of constraints.

Constraint Satisfaction Problem in AI Example

Constrains Graph

Constrains Graph


{Red, Green, Blue{

{1≠2, 1≠3, 2≠4, 3≠4}

Constraint Satisfaction Problem in AI Example

Post a Comment

* Please Don't Spam Here. All the Comments are Reviewed by Admin.

Top Post Ad

Below Post Ad

Ads Section