CSP

Question 1

Provide the definition of a constraint satisfaction problem (CSP)

Answer 1

6 - 2 to 5

Question 2

unary vs binary vs global constraint

Answer 2

6 - 12

Question 3

What is backtracking search? Provide the pseudocode

Answer 3

6 - 22 to 23

Question 4

Define the minimum remaining values heuristic

Answer 4

6 - 30

Question 4

Define the degree heuristic

Answer 4

6 - 31

Question 5

What is chronological backtracking?

Answer 5

6 - 35

Question 6

Define the least constraining value - Succeed first

Answer 6

6 - 32

Question 7

What is backjumping?

Answer 7

6 - 36

Question 8

To avoid the reduntant work, we can record the no-good by adding a new constraint in the CSP. What is the no-good?

Answer 8

6 - 37

Question 9

Illustrate the idea behind forward checking

Answer 9

6 - 39

Question 10

What forward checking cannot see? How can we solve this issue?

Answer 10

6 - 44

Question 11

Define node consistency

Answer 11

6 - 46

Question 12

Define arc consistency

Answer 12

6 - 48

Question 13

Provide an example of a constraint satisfaction problem which is arc consistent but not consistent

Answer 13

6 - 55

Question 14

What are the benefits of AC-3?

Answer 14

6 - 56

Question 15

Idea of the min conflict LS procedure

Answer 15

6 - 65

Question 15

Define path consistency for a two variable set

Answer 15

6 - 57

Question 16

What is constraint weighting?

Answer 16

6 - 72

Question 17

Why is decomposition important for CSP?

Answer 17

6 - 77

Question 18

In what way we can use the structure of a problem?

Answer 18

It can be used to find solutions quickly. For instance by finding independent subproblem they can be decomposed and solved independently

Question 19

Provide the formal definition of directed arc consistency

Answer 19

6 - 78

Question 20

How a tree-structured CSP can be solved?

Answer 20

6 - 80

Question 21

If a constraint graph is almost like a tree, what can we do to transform it? What is the name of the technique?

Answer 21

6 - 84

Question 22

Describe how the tree decomposition works and what are the conditions that need to be followed

Answer 22

6 - 85 to 87

Question 23

Given a constraint graph, how many tree decomposition you can build?

Answer 23

several

Question 24

What is the tree width of a tree decomposition?

Answer 24

Is s-1 where s is the size of the largest subproblem

Question 25

What is the tree width of a graph?

Answer 25

The minimum tree width among all its tree decompositions