4 - CSP

Question 1

Constrained Satisfaction Problems (CSPs) use ________.

Answer 1

Constrained Satisfaction Problems (CSPs) use FACTORED REPRESENTATION OF EACH STATE.

Question 2

Positive Goal Test

Answer 2

Variable satisfies all constraints

Question 3

Unary Constraint + Example

Answer 3

Involves SINGLE variable (SA != green)

Question 4

Binary Constraint + Example

Answer 4

Involves PAIRS of variables (SA != WA)

Question 5

Higher-Order Constraint + Example

Answer 5

Involves 3+ variables (SA != WA && WA != NT)

Question 6

Higher-Order constraints can be rewritten as ________.

Answer 6

… BINARY CONSTRAINTS

Question 7

Backtracking Search

Answer 7

Assign all possible values to node and continue with next node. (DFS for CSPs)

Question 8

Minimum Remaining Value Heuristic

Answer 8

Choose the variable with the fewest possible values first (-> prune search tree)

Question 9

Arc-Consistency

Answer 9

Every value x_i in D_i has a counterpart x_j in D_j that satisfies the binary constraint (Ex.: Y = X^2)

Question 10

Least Constraining Value Heuristic

Answer 10

Select value that maximizes the remaining possible values for the next nodes (-> select first value)

Question 11

Degree Heuristic

Answer 11

Assign variable involved with most constraints on other unassigned values first

Question 12

Inference

Answer 12

Reduce assignable domain values based on logical/trivial conclusions

Question 13

Tree-structured CSPs can be solved in ________ iff ________.

Answer 13

Tree-structured CSPs can be solved in O(nd^2) TIME iff the CONSTRAINT GRAPH HAS NO LOOPS.

Question 14

Tree Decomposition for nearly tree-structured CSPs

Answer 14

Decomposing the CSP into a set of connected subproblems

Question 15

Conditioning for nearly tree-structured CSPs

Answer 15

Instantiate a variable and prune its neighbors’ domains

Question 16

________ and ________ can partially transform a problem into a tree-structured one.

Answer 16

CONDITIONING and TREE DECOMPOSITION

Question 17

The complexity of solving CSPs strongly depends on the ________.

Answer 17

STRUCTURE OF their CONSTRAINT GRAPH