AI 7000 Class

Terms and Definitions from AI-7000 class

Constraint Satisfaction Problem

A problem defined by a set of variables, each with a domain of possible values, and a set of constraints specifying allowable combinations of values.

CSP

A shorthand for Constraint Satisfaction Problem.

Variables

Entities in a CSP that can take on values from their respective domains.

Domains

The set of possible values that each variable in a CSP can assume.

Constraints

Rules that specify which combinations of variable assignments are valid.

Assignment

The mapping of variables to values in a CSP.

Partial Assignment

An assignment in which some, but not all, variables have been given values.

Complete Assignment

An assignment in which every variable has been assigned a value.

Consistency

A property of an assignment where no constraints are violated.

Arc Consistency

A condition where for every value of one variable, there exists a consistent value in connected variables.

Node Consistency

A condition where each variable's values satisfy its unary constraints.

Forward Checking

A CSP solving technique that eliminates inconsistent values from domains ahead of time during search.

Backtracking Search

A depth-first search algorithm that assigns variables sequentially and backtracks upon conflicts.

Constraint Propagation

The process of enforcing constraints to reduce the search space by removing inconsistent values.

Heuristics

Rules or strategies used to improve search efficiency in CSPs.

Minimum Remaining Values (MRV)

A heuristic that selects the variable with the fewest remaining legal values first.

Degree Heuristic

A heuristic that selects the variable involved in the largest number of constraints with unassigned variables.

Least Constraining Value

A heuristic that chooses the value that rules out the fewest options for neighboring variables.

Constraint Graph

A graph representation of a CSP where nodes are variables and edges represent constraints.

Binary CSP

A CSP where all constraints involve exactly two variables.

N-ary CSP

A CSP where constraints can involve more than two variables.

Global Constraint

A constraint that involves many variables and captures a common pattern, like AllDifferent.

AllDifferent Constraint

A global constraint that requires all variables in a set to take unique values.

Unary Constraint

A constraint involving only a single variable.

Soft Constraint

A constraint that is desirable but not mandatory; violations are allowed with a cost.

Hard Constraint

A constraint that must be strictly satisfied in any solution.

Solution Space

All possible assignments of variables that could potentially satisfy the constraints.

Search Tree

A tree representing the exploration of variable assignments during CSP solving.

Conflict Set

The set of variables involved in a conflict during search.

Local Search

Search methods that iteratively improve a complete assignment by making local changes.

Hill Climbing

A local search algorithm that moves to the neighbor with the best improvement in a given evaluation function.

Simulated Annealing

A probabilistic local search that occasionally accepts worse solutions to escape local optima.

Min-Conflicts Algorithm

A heuristic repair method for CSPs that chooses variable values minimizing the number of conflicts.

Constraint Network

A graphical representation of CSPs showing variables, domains, and constraints.

Domain Pruning

The process of removing values from variable domains that cannot participate in any solution.

Inference

The act of deducing variable assignments or domain reductions from constraints.

Backjumping

A backtracking optimization that jumps back more than one level in the search tree when a dead-end is reached.

MAC (Maintaining Arc Consistency)

A backtracking algorithm that enforces arc consistency after every assignment.

Optimization CSP

A CSP where the goal is to find the best solution according to a cost or utility function.

Max-CSP

A CSP where the objective is to maximize the number of satisfied constraints.

Weighted CSP

A CSP where constraints have weights representing their importance or cost of violation.