CSP Flashcards
Provide the formal definition of a constraint satisfaction problem (CSP)
CSP Definition:
- Set of variables X={X_1,…,X_n }
- Set of domains D={D_1,…,D_n }
- D_i consists of a set of allowable values for variable X_i.
- In many cases the domain is assumed to be the same for all variables
-
Set of constraints C={c_i=(scope_i, rel_i)│i=1,…,h}
- scope_i: subset of X, the variables that are constrained by c_i
- rel_i: is a relation and tells us which simultaneous assignments of values to variables in scope_i are allowed.
Dare la definizione di soluzione di un CSP
State: defined by an assignment of values to some or all of the variables.
Assignment can be:
- Consistent: it does not violate any constraints
- Complete: every variable is assigned
- Partial: only some of the variables are assigned
Solution: a consistent and complete assignment
Che cosa `e un vincolo globale? Fare un esempio.
Global: involve an arbitrary number of variables
e.g., Alldiff, which says that all of the variables involved in the constraint must have different values.
Constraints involving more than three variables are more expressive than constraints involving only two variables? Motivate your answer.
No because every CSP can be translated into a binary CSP,
Descrivere l’euristica MRV (minimum remaining values) per i problemi di soddisfacimento di vincoli. Tale euristica viene anche chiamata euristica First-Fail.
Backtracking search: Depth-first search for CSPs with single variable assignments.
It chooses values for a not assigned variable at each level and backtracks when a variable has no legal values left to assign.
Minimum remaining values (MRV) heuristic: chooses the variable with the fewest legal values. It will fail earlier.
Descrivere l’euristica di grado (degree heuristic).
Backtracking search: Depth-first search for CSPs with single variable assignments.
It chooses values for a not assigned variable at each level and backtracks when a variable has no legal values left to assign.
Degree heuristic: chooses the variable involved in the most constraints with unassigned variables. Reduce the branching factor.
Assume there is a binary constraint between the variables X and Y. What does it mean that X is arc consistent w.r.t. Y?
It means that for each value x in the domain of X, there is some value y in the domain of Y that satisfies the constraint between X and Y.
How can we enforce X to be arc-consistency w.r.t. Y?
Remove all the values x in the domain of X for which there is no corresponding value y in the domain of Y that satisfies the constraint between X and Y.
What are the possible outcomes of the arc consistency algorithm? Explain also how these outcomes are related to the set of the solutions.
- At least one domain could be empty, in which case there is no solution
- Each domain could have a single value, in which case there is a unique solution
- Or some domains could have multiple values.
If the domains are multiple, there cannot be no solution, can be one solution or can be multiple
Consider the case where the arc consistency algorithm applied to a CSP terminates and some domains have multiple values. Is there guaranteed to be a solution? Justify the answer.
arc consistency only prune the search space, sometimes, in some lucky case, you can have as outcome a solution, if the domain of every variable is a singleton, or a failure, if at least one domain is empty, but the arc consistency never ensure the solution.
An example could be the arc consisten csp in the figure, that does not have a solution.
Provide an example of a constraint satisfaction problem which is arc consistent but with no solution.
3 variables: A,B,C
Domain for each ={1,2}
Constraint: A!=B, B!=C, C!=A
What does it mean that a two-variable set {Xi;Xj} in a CSP is path-consistent with respect to a third variable Xm.
…
Indicare quando il grafo dei vincoli `e un albero.
A constrained graph is a tree when any two variables are connected by only one path.
Definizione di directed arc consistency
A CSP is defined to be directed arc-consistent (DAC) under an ordering of variables X_1,X_2,…,X_n iff every X_i is arc-consistent with each X_j for j>i
Che cosa `e la tree width di una tree decomposition?
A constraint graph allows for several tree decompositions.
Aim: to select decomposition with the subproblems as small as possible
Tree width of a tree decomposition = s-1, where s is the size of largest sub-problem
Tree width of a graph w= the minimum tree width among all its tree decompositions.
