Constraint satisfaction problems

Question 1

What is a constraint satisfaction problem (CSP)?

Answer 1

• A set of n variables V₁, V₂, . . . , V_n.
• For each V a domain D specifying the values that V can take.
• A set of m constraints C₁, C₂, …, C_m. Each C specify an allowable collection of values for a particular set of variables.

We seek for a consistent and complete assignment. That is, an assignment that violates no constraint and assigns values to every variable.

Question 2

1. In a CSP, what variables should we assign first?
2. If there is tie in assignment, what strategy can we use to break the tie?
3. In what order shall values be assigned?

Answer 2

1. We assign the most constrained variable (aka minimum remaining value heuristic)
2. The degree heuristic chooses the variable involved in the most constraints on as yet unassigned variables.
3. Least constraining value: Pick the value that leaves maximum possible freedom to neigbours.

Question 3

Explain arc consistency, and describe how to make use of it in constraint propagation.

Answer 3

Question 4

Describe Gaschnig’s algorithm.

Answer 4

Question 5

What is graph-based backjumping.

Answer 5

When we initially detect a conflict, jump back to the parent node. If there is no conflict, we try to find the bottleneck with these dirty tricks.