CSC384: Introduction to Artificial Intelligence Search: Constraint Satisfaction Problems
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSC384: Introduction to Artificial Intelligence
Search: Constraint Satisfaction Problems
Practice Problems
1. True or False: Deleting values from the domains of CSP variables that prevent the constraint graph from being arc consistent will never rule out a possible solution to the CSP.
2. State the condition under which an constraint that operates over two variables (X,Y) is generalized arc consistent.
3. Consider the map shown below. There are five regions, and the following informa- tion is available about what they can represent:
❼ R1 can only be the sky or grass
❼ R2 can only be trees or a road
❼ R3 can only be grass or trees
❼ R4 can only be road or grass
❼ R5 can only be a car
|
R1 |
|
|
Furthermore, we have the following knowledge about the real world, and the map:
❼ A car cannot be next to grass
❼ No two neighboring regions can be the same
❼ Only one region is a road
The problem is to find what each region in the figure represents.
(a) Represent the above problem as a CSP. You must specify the meaning of each
variable assignment (i.e., in our representation, how can one read off a solution to the problem from an assignment of values to the variables).
(b) Apply forward checking to solve the problem. Use the heuristic of always
assigning next the variable with fewest remaining values (you can break ties as you choose).
(c) How many solutions are there, and what are they?
4. Consider a CSP with variables, V, and constraints C, where
❼ V = {A,B,C,D,E}
❼ domV = {1, 2, 3, 4},V ∈ V
❼ C = {C1 , . . . ,C7 }, where
– C1 : E − A must be even1
– C2 : C 
D
– C3 : C > E
– C4 : C 
A
– C5 : B > D
– C6 : D > E
– C7 : B > C
(a) Draw these variables and constraints as a constraint graph.
(b) Enforce arc consistency the graph. Write the domains for each variable that
exist after you’ve completed it.
2022-06-21