7. Constraint Satisfaction Problems Flashcards
What is a Constraint Satisfaction Problem (CSP)?
A problem where the goal is to find an assignment of values to variables that satisfies all given constraints.
Give examples of CSPs.
Sudoku, map coloring, job scheduling, N-Queens, crossword puzzles, cryptarithmetic, and transportation scheduling.
What defines the state of a CSP?
A set of variables with values from a domain and constraints restricting allowable combinations.
What are discrete variables in CSPs?
Variables with finite or infinite domains, such as Boolean values, colors, or strings for crossword puzzles.
What are continuous variables in CSPs?
Variables with infinite domains, such as start/end times in scheduling problems.
What are the types of constraints in CSPs?
Unary (applied to a single variable), binary (between two variables), global (involving multiple variables), and alldiff (ensuring all values are unique).
What is the difference between hard and soft constraints?
Hard constraints must be strictly followed, while soft constraints express preferences with associated costs.
What is a hypergraph in CSPs?
A graph representation where variables are nodes and constraints are edges between them.
What is a standard search formulation for solving CSPs?
Using uninformed search algorithms like DFS or BFS, treating variable assignments as states and checking constraints incrementally.
What is chronological backtracking search?
A DFS-based approach that assigns values step by step while ensuring constraints are met.
What is forward checking in CSPs?
A filtering technique that removes inconsistent values from future variable domains to reduce backtracking.
What is arc consistency?
A constraint propagation technique ensuring that every value in a variable’s domain has a consistent value in a connected variable’s domain.
What is the Minimum Remaining Values (MRV) heuristic?
A variable ordering strategy that selects the variable with the fewest remaining legal values.
What is the Degree Heuristic?
A variable ordering strategy that selects the variable involved in the most constraints.
What is the Least Constraining Value (LCV) heuristic?
A value ordering strategy that selects the value that eliminates the fewest options for neighboring variables.
What is backjumping in CSPs?
A technique that jumps back to the most recent conflict instead of backtracking step-by-step.
What is conflict-directed backjumping?
A method where each variable maintains a conflict set, migrating conflicts to earlier variables to find a valid assignment.
How can problem structure improve CSP solving?
Breaking CSPs into independent sub-problems or using cutset conditioning to simplify the constraint graph.
What is cutset conditioning?
A method where certain variables are instantiated to transform the constraint graph into a tree, reducing complexity.
