CSP Flashcards
Provide the definition of a constraint satisfaction problem (CSP)
6 - 2 to 5
unary vs binary vs global constraint
6 - 12
What is backtracking search? Provide the pseudocode
6 - 22 to 23
Define the minimum remaining values heuristic
6 - 30
Define the degree heuristic
6 - 31
What is chronological backtracking?
6 - 35
Define the least constraining value - Succeed first
6 - 32
What is backjumping?
6 - 36
To avoid the reduntant work, we can record the no-good by adding a new constraint in the CSP. What is the no-good?
6 - 37
Illustrate the idea behind forward checking
6 - 39
What forward checking cannot see? How can we solve this issue?
6 - 44
Define node consistency
6 - 46
Define arc consistency
6 - 48
Provide an example of a constraint satisfaction problem which is arc consistent but not consistent
6 - 55
What are the benefits of AC-3?
6 - 56
Idea of the min conflict LS procedure
6 - 65
Define path consistency for a two variable set
6 - 57
What is constraint weighting?
6 - 72
Why is decomposition important for CSP?
6 - 77
In what way we can use the structure of a problem?
It can be used to find solutions quickly. For instance by finding independent subproblem they can be decomposed and solved independently
Provide the formal definition of directed arc consistency
6 - 78
How a tree-structured CSP can be solved?
6 - 80
If a constraint graph is almost like a tree, what can we do to transform it? What is the name of the technique?
6 - 84
Describe how the tree decomposition works and what are the conditions that need to be followed
6 - 85 to 87
Given a constraint graph, how many tree decomposition you can build?
several
What is the tree width of a tree decomposition?
Is s-1 where s is the size of the largest subproblem
What is the tree width of a graph?
The minimum tree width among all its tree decompositions
