Week 7 - CSP

What defines a constraint satisfaction problem (CSP)?

A CSP is defined by variables, domains (possible values for each variable), and constraints (relationships among variables).

What is a constraint graph?

A graph where nodes represent variables and edges represent constraints between them.

What are unary, binary, and higher-order constraints?

Unary: constraints on a single variable; Binary: constraints between two variables; Higher-order: constraints involving 3+ variables.

What is backtracking search in CSPs?

A depth-first search that assigns values to one variable at a time, backtracking when a constraint is violated.

What is the Minimum Remaining Values (MRV) heuristic?

Selects the variable with the fewest legal values left.

What is the Degree heuristic in CSPs?

Among variables with same MRV, selects the one with the most constraints on remaining variables.

What is the Least Constraining Value (LCV) heuristic?

Selects the value that rules out the fewest values in neighboring variables.

What is forward checking in CSPs?

It eliminates inconsistent values from neighbor domains after each assignment to detect dead-ends early.

What is arc consistency?

An arc X → Y is consistent if for every value x in X, there exists some value y in Y satisfying the constraint.

What is the AC-3 algorithm used for?

To enforce arc consistency across all arcs in a CSP by iteratively removing inconsistent values.

What is the advantage of identifying independent subproblems in CSPs?

Solving smaller, independent subproblems reduces overall complexity from exponential to linear in number of subproblems.

What is a tree-structured CSP?

A CSP where the constraint graph has no loops; can be solved in linear time O(nd²).

What is cutset conditioning?

Instantiating a small set of variables to turn a general CSP into a tree-structured one for fast solving.

What is local search in CSPs?

Start with a complete assignment and iteratively change variable values to minimize constraint violations.

What is the min-conflicts heuristic?

At each step, select a conflicted variable and assign it the value that results in the fewest constraint violations.

What is the run time of AC-3

O(nd²)