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
What is the Least-Constraining Value rule?
Choose the value that rules out the fewest choices for neighbour variables
What is Forward Checking?
after a variable is assigned in backtracking search, we can rule out all domain values for associated variables that are inconsistent with the assignment
What is the basic idea of a local min search?
- Assign all the variables
- Modify assignments to make it better
What is the maximum value of n in the n-queens problem what was solved by local search in under a minute
3 million
