7 - Constraint Satisfaction Problems

Question 1

What is a Constraint Satisfaction Problem (CSP)?

Answer 1

A problem, that requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied

Question 2

How do we formulate a CSP?

Answer 2

Initial state- empty assignment: all variables are unassigned.
Successor function - assigns value to an unassigned variable that does not conflict with previously assigned variables
Goal test - complete current assignment
Path cost - constant cost per step

Question 3

What is a Backtracking search?

Answer 3

Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end.

To improve this method, we can ask ourselves: Which variable should be assigned next?In what order should its values be tried? *Can we detect inevitable failure early?

Question 4

What is Constraint propagation?

Answer 4

Forward checking propagates information from assigned to unassigned variables, but doesn’t provide early detection for all failures

Question 5

Arc consistency

Answer 5

Simplest form of propagation makes each pair of variables consistent: X →Yis consistent ifffor everyvalue of X there is someallowed value of Y