Constraint Satisfaction Problems Flashcards

1
Q

State in CSP

A

state is defined by variables, X, with values from domain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

goal test in CSP

A

set of constraints specifying allowable combinations of values for subsets of variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Variable based model

A

Solution is not a path but an assignment of values for a set of variables that satisfy all constraints

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Complete solution

A

all variables are assigned values. Solutions are complete and consistent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

consistent solution

A

does not violate any constraints. Solutions are complete and consistent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Constraint graph

A

nodes are varialbes, arcs are constraints

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Varieties of CSPs

A

discrete variables - finite and infinite domains

continuous variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

unary constraints

A

constraints involve a single variable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

3 types of constraints

A

unary, binary, high order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

binary constraints

A

involve pairs of variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

higher-order constraints

A

involve 3 or more variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

apply local search for CSPs

A

allow states with some unsatisfied constraints; operators assign a value to a variable; variable selection, value selection

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

min conflicts heuristic

A

choose value that violates the fewest constraints

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

min-conflicts algorithm

A

Assign each variable a random value, defining the inital state
While state is not consistent: pic a variable that has a constraint violated, find a value for the variable that minimizes the total number of violated constraints (ver all variables)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Min Conflicts Algorithm Advantages

A

Simple and fast

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Min Conflicts Algorithm Disadvantages

A

Only searches states that are reachable from the initial state (might not search entire state space); does not allow worse moves; not complete

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

CSP Tree Search Formulation

A

initial state: empty assignment
successor function: assign a value to an unassigned variable
goal test: the current assignment is complete: all variables assigned a value and all constraints satisfied

18
Q

Why isn’t cost important for CSP?

A

Find any solution

19
Q

every solution appears at depth

A

at depth n with n variables

20
Q

variable assignments are

A

commutative

21
Q

generate and test strategy

A

generate candidate solutions, then test if it satisfies all constraints

22
Q

How to improve DFS for CSP

A

backtracking with consistency checking

23
Q

backtracking with consistency checking for successors

A

don’t generate a successor that creates an inconsistency with any existing assignment - perform consistency checking when a node is generated

24
Q

back tracking with consistency checking successor function

A

assigns a value to an unassigned variable that does not conflict with all current assignments (fails if no legal assignments); the uninformed search of CSPs

25
Backtracking with consistency checking algorithm
Start with empty state while not all vars in state assigned a value: pick a variable, if it has a value that does not violate any constraints, then assign that value else: go back to previous variable and assign it another value
26
Is backtracking search complete?
Yes; will find a solution if one exists, might expand the entire search space
27
Summary of backtracking search
depth first search algorithm: goes down 1 variable at a time, at deadend, backs up to the last variable whose value can be changed w/o violating constraints and changes it, if you backed up to root and tried all values, then no solutions
28
How to improve backtracking efficiency?
Heuristics: | Which variable assigned next, what order of values tried, early detection of failure
29
Which variable next?
Most constrained variable | Most constraining variable
30
most-constrained variable
choose the variable with the fewest remaining moves, aka minimum remaining values heuristic; minimizes branching factor
31
most-constraining variable
tie breaker for most constrained variable; choose the variable with the most constraints on the remaining variables; aka degree heuristic
32
Which value next?
Least-constraining value
33
least-constraining value
try to pick best values first; value that rules out the fewest values in the remaining variables
34
Improve CSP
DFS with consistency checking/heuristics | Forward Checking
35
Forward Checking
At start, record set of all possible legal values for it; when assign a value to variable, update the set of legal values for all unassigned variables; backtrack immediately if empty set of possible values
36
Forward Checking Algorithm idea
keep track of remaining legal values for all variables; deaded when any variable has no legal values
37
Why constraint propagation?
Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures
38
constraint propagation main idea
When you delete a value from a variable's domain, check all variables connected to it; if any of them change, delete all inconsistent values connected to them; etc
39
arc consistency
x->y is consistent iff: for every value x at X there is some allowed y, if not, delete x (if x loses a vlue, all neighbors of X need to be rechecked)
40
Arc Consistency Algorithm
hold
41
How to combine search with CSP:
at each node in DFS search assign a selected value to a selected variable; run CSPto reduce variables' domains and check if any inconsistencies arise as a result of this assignment
42
Combining Backtracking search with CSP algorithm
hold