Introduction to Constraint Satisfaction Problems and Local Search

Vocabulary flashcards covering Constraint Satisfaction Problems (CSP), variable elimination, and local search optimization strategies from Chapter 1 to 7.

Constraint Satisfaction Problem (CSP)

A problem where the solution is an assignment of values to variables that satisfy all constraints, focusing on the goal state rather than the search path.

Forward Checking Algorithm

A method used to improve backtracking by detecting potential failures earlier in the search process.

AC-3 Algorithm

An algorithm used to increase efficiency in CSPs by utilizing the concept of arc consistency.

Domain Splitting

A modification that breaks a large search space into smaller subspaces by splitting a variable’s domain into two or more sub-domains, enabling parallel solving.

Variable Elimination

An algorithm that eliminates variables from constraints one by one to create more complex constraints with fewer variables until one remains, then backtracks to infer values.

Projecting

A step in variable elimination where a joined constraint is mapped onto all involved variables except for the variable currently being eliminated.

Local Search

Strategies that focus on finding an optimal configuration by maintaining only current assignments rather than tracking the entire path to a goal.

Evaluation (Heuristic) Function

A criteria in optimization problems, such as the number of violated constraints, used to determine if a state is becoming better or worse.

Iterative Best Improvement (IBI)

A greedy local search algorithm that evaluates all possible neighbors and selects the one that best minimizes or maximizes the heuristic function.

n-Queens Problem

A puzzle where $n$ queens must be placed on an $n \times n$ board so that no two queens attack each other horizontally, vertically, or diagonally.

Simple Hill Climbing

A local search approach that examines one neighbor at a time and moves to the first state that shows improvement rather than evaluating all neighbors.

Local Minimum

A point in a search space where no neighboring state improves the evaluation criteria, potentially causing a local search to get stuck.

Diagonal Ridges

A search problem where a series of steps must temporarily make the heuristic evaluation worse before it can eventually become better.

Hill Climbing with Side Moves

A variation of hill climbing that allows transitions to neighboring states even if the heuristic value remains the same.

Tabu Search

A search strategy that maintains a "taboo list" of recently visited states to prevent the algorithm from returning to them and to help it escape local minima.