Introduction to Constraint Satisfaction and Local Search

This set covers vocabulary and concepts from the lecture on improving backtracking, the Variable Elimination algorithm, and various Local Search strategies for optimization.

Constraint Satisfaction Problem

A search problem where the solution is an assignment of values to variables that satisfies all constraints, focusing on the goal state's properties rather than the path taken to reach it.

Forward Checking

An early failure detection algorithm that improves backtracking by checking the remaining possible values for variables after an assignment is made.

AC-3 Algorithm

An efficiency-improving algorithm used with backtracking that leverages the concept of arc consistency to reduce the search space.

Domain Splitting

A modification for backtracking where a large variable domain is split into smaller sub-domains, allowing the search space to be broken down and solved separately or in parallel.

Variable Elimination

An algorithm that simplifies a problem by choosing a variable, joining all constraints it appears in, and projecting that result onto the other variables to eliminate it until only one variable remains.

Local Search

A search strategy for optimization problems that does not track paths but moves between configurations to find a state that minimizes or maximizes a specific criterion.

Iterative Best Improvement

A greedy local search approach that evaluates all possible neighbor states and chooses the one that best improves the optimization criteria.

Heuristic Function

An evaluation function in local search that indicates whether a change in state brings the agent closer to the goal or makes it 'happier.'

n-queens Problem

A standard problem used to demonstrate search algorithms where $n$ queens must be placed on an $n \times n$ board such that they cannot attack each other vertically, horizontally, or diagonally.

Hill Climbing

A local search algorithm that iteratively moves to a neighbor with a better heuristic value, often stopping when no improving successor exists.

Simple Hill Climbing

A variation of hill climbing that jumps to the first improvement it finds rather than evaluating every possible neighbor option.

Local Minimum

A point in the search space where the heuristic cannot be improved by moving to any immediate neighbor, causing a local search to get stuck even if a global optimum exists.

Ridges

A search space challenge where an algorithm must temporarily move to a state with a worse heuristic value in order to eventually reach a better solution.

Hill Climbing with Side Moves

A modification that allows the algorithm to move to a neighbor state with the same heuristic value to avoid getting stuck on plateaus or shoulders.

Taboo Search

A local search method that maintains a 'taboo list' of previously visited states to avoid cycles and help the algorithm escape local minima.