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
{1,2,3,4}
{Red, Green, Blue{
{1≠2, 1≠3, 2≠4, 3≠4}
