Title: EAI / 09_constraints

Q: What are the ingredients for a constraint satisfaction problem?
A: - a state which is defined by variables with values from an associated domain
- a goal test, defined by a set of constraints specifying allowable combinations of values for subset of variables

Q: What is a consistent assignment?
A: An assigment that does not violate any constraints.

Q: If the maximum domain size of any variable in a CSP is \(d\), and there
are \(n\) variables, what is the number of possible complete assignments?
A: \(\mathcal{O}(d^n)\)

Q: Which property do non-linear constraints have?
A: Non-linear constraints are undecidable.

Q: With which method and how fast can linear constraints be solved?
A: Wtih linear programming methods in polynomial time.

Q: Which search algorithsm can solve CSPs?
A: Any standard search algorithm can be used to solve CSPs.

Q: What property helps in reducing a tree with \(n!d^n\) to \(d^n\) leaves?
A: Commutivity of variable assignments; the order doesn't matter.

Q: What algorithm does backtrackng search for CSPs (with single variable assignments) use?
A: Depth-first search

Q: Explain the minimum-remaining-values (MRV) heuristic.
A: Choose the variable with the fewest legal values.

Q: Explain the degree heuristic.
A: Select the variable that is involved in the largest number of constraints on other unassigned variables.

Q: Explain the least-constraining-value heuristic.
A: The least-constraining-value heuristi prefers a value that rules out the fewest choices for the neighbouring variables in the constraint graph.

Q: What is forward checking?
A: - Whenever a varialbe \(X\) is assigned, it looks at each unassigned variable \(Y\) that is connected to \(X\) by a constraint
- And deletes from the domain of \(Y\) any value that is inconsistent with the value chosen from \(X\)

Q: What is constraint propagation?
A: Constraint propagation is the general term for propagating the implications of a constraint on one variable onto other variables.

Q: Explain Arc consistency.
A: - "arc" refers to a directed arc in the constraint graph;
- \(X \rightarrow Y\) is consistent iff for every value \(x\) of \(X\) there is some allowed value \(y\) of \(Y\)