Final CSP Flashcards
Q1. How many states can be represented by eight variables, each of which can take four values?
Answer: Number of possible stated equals to domain size^number of variables. In this case all variables have the same domain size so answer is 4^8 = 65536
Q2. How many states can be represented by three variables, each of which can take three values? How many states are there for a 3-queen problem?
Answer: 3^3 = 9 states. For 3-queen problem: 3 variables (queens), 3x3 size of the grid. So the number of possible worlds (excluding overlaps) = (9 3) = 9!/(6!*3!)
Q3. State the condition under which an arc is arc consistent.
Answer: An arc <x> 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.</x>
Q4. How can we enforce consistency of an arc ?
Answer: We can remove all values x in dom(X) for which there is no corresponding value in dom(Y). This removal will never rule out any of models/solutions.
Q5. What does it mean for a network to be arc consistent?
Answer: A network is arc consistent if all its arcs are arc consistent.
Q6. What are the possible outcomes of the arc consistency algorithm?
Answer: First outcome: at least one of X,Y,Z has empty domain. No solution.
Second outcome: all X,Y, and Z have single value domain. Unique solution.
Third outcome: some of X,Y,Z have more than one value in the domain. Needs to be solved as smaller CSP problem.
Q7. Consider the constraint graph in Figure 1. Imagine that arc consistency has just reduced the domain of X as a result of considering the edge <x>. Do we have to add the edge <x> back to the list of “to-do arcs"? Explain why or why not (i.e., don't just state a rule given in class).</x></x>
Answer: No, arc <x> is still consistent as the domain of X reduced, but there are still values on dom(Z) (those are unchanged) that correspond to all of the values in dom(X). So this edge is still arc consistent.</x>
Q8. Consider the constraint graph in Figure 1. Imagine that arc consistency has just reduced the domain of X as a result of considering the edge <x>. Do we have to add the edge <y> back to the list of “to-do arcs"? Explain why or why not (i.e., don't just state a rule given in class).</y></x>
Answer: Yes, the domain of X was reduced, so some values that corresponded to values in dom(Y) may not be in dom(X) anymore. That means that this arc may not be arc consistent anymore.
Q9. Consider the constraint graph in Figure 1. Imagine that arc consistency has just reduced the domain of X as a result of considering the edge <x>. Do we have to add the edge <z> back to the list of “to-do arcs"? Explain why or why not (i.e., don't just state a rule given in class).</z></x>
Answer: Yes, the domain of X was reduced, so some values that corresponded to values in dom(Z) may not be in dom(X) anymore. That means that this arc may not be arc consistent anymore.
Q10. Consider the following statement: every problem that can be defined as a CSP where variables have finite domains and with a finite number of variables can also be defined as a search problem using a state-based representation. Explain why it is true or false; if true, explain what would correspond to a state, and if false, give a counter-example.
Answer: True, state would be an assignment of values to variables.
Q11. How can a CSP be solved by search (specify states, neighbors, start state, goal state). What search strategy would you use? Why?
Answer: CSP problem can be formulated as a search problem. In this case states are partial assignments of values to variables, neighbors - states with next variable assigned , start state - empty assignment, goal state - complete assignment of values to variables that satisfy all the constraints. Most appropriate search strategy in this case would be dfs as all solutions are on the same depth, there are no cycles, and branching factor depends on the size of domain of variables (may be huge).
