Constraint Satisfaction Problems and Backtracking Improvements

These vocabulary flashcards cover key heuristics and algorithms for solving Constraint Satisfaction Problems (CSPs), including backtracking enhancements and consistency checks discussed in Lecture 11.

Backtracking Algorithm

A search algorithm that applies depth-first search (DFS) by assigning values to variables one by one and backtracking when a value assignment violates a constraint.

Minimum Remaining Value (MRV) Heuristic

A heuristic that selects the variable with the fewest legal values remaining in its domain to assign next.

Degree Heuristic

A tie-breaker heuristic that chooses the variable with the most constraints on the remaining unassigned variables.

Least Constraining Value (LCV) Heuristic

A heuristic that chooses the value for a variable that eliminates the fewest options from the domains of other variables to preserve future search possibilities.

Forward Checking

An improvement to backtracking that keeps track of remaining legal values for unassigned variables and terminate the search early if any variable’s domain becomes empty.

Arc Consistency

A condition where for every value in a domain $d_i$ of variable $x_i$, there exists some value in domain $d_j$ of variable $x_j$ that satisfies the binary constraint between them.

AC-3 Algorithm

A recursive procedure that propagates arc consistency by maintaining a queue of arcs and removing inconsistent values from variable domains until the queue is empty.

Binary Constraint

A constraint involving a relationship between exactly two variables.

Unary Constraint

A constraint that limits the possible values of a single variable independently of other variables.

Variable Elimination Algorithm

A method for solving constraint satisfaction problems that differs from backtracking by systematically eliminating variables from the problem.

Commutative Property

A property of constraint satisfaction problems where the order of assigning values to variables does not affect the final assignment reaching a solution.

Tie-breaker

The use of a secondary heuristic, such as the Degree Heuristic, to choose between variables that have the same value for the primary heuristic like MRV.