Consider the following CSP. A, B, C and D are variables with their domain of values...

Transcribed Image Text:

Consider the following CSP. A, B, C and D are variables with their domain of values as given below: A = {1, 2, 3} B = {1,2,3,4) C = {1,2,3} D = {1,2} The constraints are: = AB {(1,1), (2,2), (3,3)} AD {(1,2), (2,1), (3,1)} BC = {(1,3), (2,1), (4,1), (4,2)} DC={(1,1), (1,3), (2,2)} (a) What is the size of the search space for the CSP? (b) Illustrate how the following search techniques will proceed to find a solution for the CSP? 1) backtracking search 2) backtracking search with forward checking and 3) arc consistency with forward checking (c) What is the size of the search space for the arc consistent CSP? Consider the following CSP. A, B, C and D are variables with their domain of values as given below: A = {1, 2, 3} B = {1,2,3,4) C = {1,2,3} D = {1,2} The constraints are: = AB {(1,1), (2,2), (3,3)} AD {(1,2), (2,1), (3,1)} BC = {(1,3), (2,1), (4,1), (4,2)} DC={(1,1), (1,3), (2,2)} (a) What is the size of the search space for the CSP? (b) Illustrate how the following search techniques will proceed to find a solution for the CSP? 1) backtracking search 2) backtracking search with forward checking and 3) arc consistency with forward checking (c) What is the size of the search space for the arc consistent CSP?