Constraint Specific Problem Problem.pptx

Constraint Specific Problem Problem

1. Constraint Satisfaction Problem Artificial Intelligence

2. Constraint Satisfaction Problems (CSP)

3. Components in CSP There are mainly three basic components in the constraint satisfaction problem: Variables : {V1, V2, V3 … Vn} Set of Domains : {D1, D2, D3, … Dn} for each variable Constraints : The guidelines that control how variables relate to one another are known as constraints. Ci = {Scope, Rel} Where scope is set of variables that participate in constraint Rel is relation that defines the values that variable can take.

4. Example. For instance, in a sudoku problem, the restrictions might be that each row, column, and 3×3 box can only have one instance of each number from 1 to 9.

5. CSP Solve using Backtracking V = {1, 2, 3, 4} D = {Red, Green, Orange} C = {1≠2, 1≠3, 1≠4, 2≠4, 3≠4} 1 2 3 4

6. CSP Solve using Backtracking V = {1, 2, 3, 4} D = {Red, Green, Orange} C = {1≠2, 1≠3, 1≠4, 2≠4, 3≠4} 1 2 3 4 1 2 3 4 Initial Domain R,G,O R,G,O R,G,O R,G,O 1=R R GO GO GO 2=G R G GO O 3=B R G O O

7. CSP Solve using Backtracking V = {1, 2, 3, 4} D = {Red, Green, Orange} C = {1≠2, 1≠3, 1≠4, 2≠4, 3≠4} 1 2 3 4 1 2 3 4 Initial Domain R,G,O R,G,O R,G,O R,G,O 1=R R GO GO GO 2=G R G GO O 3=G R G G O