Constraint Satisfaction Problems Lecture Notes

These flashcards cover the introductory concepts of Constraint Satisfaction Problems (CSPs), including their components, types of constraints, and standard solving algorithms like backtracking.

Atomic representation

A model where there is no internal structure to the nodes, and the solution is found by transitioning between states to reach a goal state, such as a Rubik's cube.

Factored representation

A model defined by a set of variables and values where the solution is the state itself that satisfies certain rules rather than a sequence of actions.

Constraint Satisfaction Problem (CSP)

A problem consisting of a set of variables $X_i$, a domain $D_i$ of possible values for each variable, and a set of constraints specifying allowed combinations of values.

Variable

In a CSP, the elements to which values are assigned, such as geographic states in map coloring or activities in factory scheduling.

Domain

The set of all possible allowed values that can be assigned to a variable, such as a set of colors (red, green, blue) or numbers from $0$ to $9$.

Constraint

A rule that specifies which combinations of assignments to variables are allowed, ensuring the solution is valid.

Unary constraint

A constraint that involves only one variable, such as stating a specific state cannot be the color red.

Binary constraint

A constraint that involves two variables, typically represented as an arc in a CSP graph between two nodes.

Higher order constraint

A constraint involving three or more variables, such as those found in complex logical expressions or cryptarithmetic summations.

Soft constraint

Representations of preferences that rank solutions based on priority, such as choosing a lecture time closer to $1\,PM$ when multiple valid slots exist.

Cryptarithmetic problem

A mathematical puzzle where letters represent digits and the objective is to assign digits so that the summation of strings (e.g., SEND + MORE = MONEY) is correct.

Generate and test algorithm

An inefficient strategy that randomly generates a potential assignment and tests it against all constraints, involving up to $10^8$ combinations in some puzzles.

Backtracking algorithm

A recursive search strategy that applies depth-first search to CSPs by assigning values to variables one at a time and reverting if a constraint is violated.

Recursion

A programming or mathematical method where a function calls itself, used in the backtracking algorithm to explore the search tree of assignments.

Optimization problem

A type of problem where the goal is to minimize or maximize a specific value; CSPs are considered a special case of these problems.

CSP Graph

A visual representation of a constraint satisfaction problem where the variables are nodes and the constraints are the arcs connecting them.