CSPs Flashcards
What are 3 problems CSPs can be used to solve?
- Graph Colouring
- Job Shop Scheduling (Putting on clothes)
- Cryptarithmetic Puzzles (TWO + TWO = FOUR)
What are the 3 main components of CSPs?
- X: a set of variables
- D: a set of domains per variable
- C: a set of constraints
A consistent or satisfied CSP is a CSP with variables ______ and constraints ___________
assigned, non-violated
What is a complete assignment?
All variables in the CSP are assigned a value
A _______ is a complete assignment that is also consistent
solution
A CSP with no solution is referred to as ____________ and a CSP with many solutions is referred to as _________
over-constrained, -under-constrained
If a domain is ______, the CSP has no solution
empty
What is the size of the search space in a CSP?
D1 * D2 * D3 * … * DN
When is a CSP variable Xi considered to be arc consistent with Xj?
If for every value Di, there is at least one corresponding value in Dj that satisfies the binary constraint on Xi and Xj
Efficient algorithms exist to make CSPs ____ _______
arc consistent
REVIEW AC3 TRACE
REVIEW AC3 TRACE
What is the basic idea of backtracking search?
- pick an unassigned variable
- assign it a value that doesn’t violate any constraints
- if there is no such value, then backtrack to the previous step and choose a new variable
A basic backtracking search is _____, but often very _____ on large problems
complete, slow
What are four sets of improvements that can be made to basic backtracking?
- Rules for choosing the next variable to be assigned
- Rules for choosing what value to assign to the current variable
- Rules for interleaving searching and inference
- Rules for choosing what variables to backtrack to
What is the Minimum Remaining Values rule?
Always choose to assign the variable with the least amount of elements in it’s domain
