CSPS (midterm) Flashcards
How many states can be represented by 8 variables, each of which can take 4 values?
4^8
How many states can be represented by 3 variables, each of which can take 3 values? States for 3-queen problem
3^3, queen 3^2 choose 3
State the condition under which an arc > is arc consistent
An arc is arc consistent if for each value x in dom(X) there is some value y in dom(Y) such that r(X,Y) is satisfied.
Consider the constraint graph in Figure 1. Imagine that arc consistency has just reduced the domain of X as a result of considering edge . Do we have to add the edge back to the list of ? Why or why not?
No, this is because all the values in X have a corresponding value in domain (Y), thus losing one value from domain(x) will not stop arc (X, c2) from being consistent.
Consider the constraint graph in Figure 1. Imagine that arc consistency has just reduced the domain of X as a result of considering edge . Do we have to add the edge back to the list of ? Why or why not?
No, it is part of the binary relation.
Consider the constraint graph in Figure 1. Imagine that arc consistency has just reduced the domain of X as a result of considering edge . Do we have to add the edge back to the list of ? Why or why not?
Yes, there may have been a value in domain(x) which another value in domain(z) was relying on to make arc < (z,c2) consistent.
How can a CSP be solved by search (specify states, neighbors, start state, end state). What search strategy would you use? Why?
CSP problems can be formulated as search problems
States: partial assignments of values to variables
Neighbors: States with next variable assigned
start state: empty assignment of variables
End state: all variable have value assignment that satisfies
the constraints
I would use DFS as all the solution exist at the same depth and there are no cycles in the tree, and branching factor could be very large depends on the size of the domain
