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

narrowing down the possible solutions early on, helping to detect conflicts and reduce unnecessary search efforts

Question 5

Arc consistency

Answer 5

ensures that for every value of one variable, there is a consistent value in another variable connected by a constraint.