Constraint Satisfaction Problems

Question 1

What is a CSP?

Answer 1

A special type of search problem with states defined by values which can come from a specific domain. The goal test is a set of constraints specifying allowable combos of values for subsets of variables

Question 2

What is backtracking search?

Answer 2

DFS with two improvements: Check one variable at a time and check constraints as you go.

Question 3

What is filtering?

Answer 3

Keeping track of domains for unassigned variables and crossing off bad options.

Question 4

What is forward-checking?

Answer 4

Crossing off values that violate a constraint when added to the existing assignment.

Question 5

What makes an arc consistent?

Answer 5

An arc is consistent if and only if for EVERY ‘x’ in the tail there is SOME ‘y’ in the head which could be assigned without violating a constraint

Question 6

True or False: If a variable loses a value, its neighbors need to be rechecked in order to reinforce arc consistency.

Answer 6

True

Question 7

What are the limitations of arc consistency?

Answer 7

You may have one, multiple, or no solutions left.