CSP (Constraint satisfaction problem) Flashcards
What is the difference between imperative and declarative solutions to problems?
Imperative: Explicitly describes how to compute a solution.
Declarative: Specifies what constraints a solution must satisfy.
In a constraint graph, what does the nodes and edges represent?
Nodes: Variables.
Edges: Constraints.
How does forward checking work?
Works by keeping track of remaining legal values for unassigned variables.
What is the weakness forward checking?
It doesn’t provide early detection for all failures.
What is an unary constraint?
A rule that applies to a single variable.
What is the purpose of node consistency?
Ensuring each variable satisfies its unary constraints
What is the requirement X and Y to be arc consistent?
X -> Y is consistent iff for every value of x of X there is some allowed y for Y.
(Detect errors earlier than forward checking)
What is the point of path consistency?
Ensuring if two variables satisfy a constraint, a third variable can still take a consistent value.
Rarely used since expensive to run.
What is the point of using a minimum-remaining values heuristic?
Quickly reducing the search space.
What is a degree heuristic, and what is the point of using it?
Picks the variable affecting most constraints.
Point: Prunes a lot of the search tree
