如果这篇博客帮助到你，可以请我喝一杯咖啡~

CC BY 4.0 （除特别声明或转载文章外）

## Constraint satisfaction problem (CSP，约束满足问题)

- The search algorithms we discussed so far had no knowledgeof the states representation (black box).
- Instead we can have a general state representation that workswell for many different problems.
- We can build then specialized search algorithms that operateefficiently on this general state representation.
We call the class of problems that can be represented withthis specialized representation CSPs – Constraint Satisfaction Problems.

- 到目前为止，我们讨论的搜索算法没有状态表示(黑盒)的知识。
- 相反，我们可以有一个适用于许多不同问题的通用状态表示。
- 我们可以构建专门的搜索算法，有效地在这个通用状态表示上操作。
- 我们把可以用这种专门的表示CSPs-Constraint Satisfaction Problems表示的问题类称为CSPs-Constraint Satisfaction Problems。

## CSPs: State Representation

The idea: represent states as a vectors of feature values

- A set ofkfeatures (or variables)
- Each variable has a domain of different values,e.g.
- height ={short, average, tall},
- weight ={light, average, heavy}

- A state is specified by an assignment of a value for eachvariable.
- A partial state is specified by an assignment of a value tosome of the variables.
- A goal state specified as conditions on the vector of featurevalues.

## Formalization of a CSP

- A CSP consists of
- A set of variablesV1, . . . , Vn
- For each variable a (finite) domain of possible values Dom[Vi].
- A set of constraintsC1, . . . , Cm.

- A solution to a CSP is an assignment of a value to all of thevariables such that every constraint is satisfied.
- A CSP is unsatisfiable if no solution exists.
- Each variable can be assigned any value from its domain
- Vi=dwhered∈Dom[Vi]

- Each constraint C
- has a set of variables it is over, called its scope,e.g.,C(V1, V2, V4)
- Acts as a boolean function that maps assignments to thesevariables to true/false,e.g.,
- C(V1=a, V2=b, V4=c) =True
- C(V1=b, V2=c, V4=c) =False

## Constraints

- Unary Constraints (over one variable)
- e.g.,C(X) :X= 2;C(Y) :Y >5

- Binary Constraints (over two variables)
- e.g.,C(X, Y) :X+Y <6

- Higher-order (n-ary) constraints: over 3 or more variables.

## Solving CSPs

- We do not care about the sequence of moves needed to get toa goal state.
- We only care about finding a setting of the variables thatsatisfies the goal.
- Thus CSPs can be solved by a specialized version of depthfirst search.
- We can build up to a solution by searching through the spaceof partial assignments.
- In principle, the order in which we assign the variables doesnot matter – eventually they all have to be assigned.
- If we falsify a constraint during the process of building up asolution, we can immediately reject the current partialassignment.

## CSP as a Search Problem

- Initial state: empty assignment
- Successor function: a value is assigned to any unassignedvariable, which does not cause any constraint to return false.
- Goal test: the assignment is complete

## A generic backtracking algorithm

- We pick a variable*,
- pick a value for it*,
- test the constraints that we can,
- if a constraint is unsatisfied we backtrack,
- otherwise we set another variable.
- When all the variables are set, we’re done.

## Backtracking Search

- The algorithm searches a tree of partial assignments.
- Heuristics are used to determine
- the order in which variables are assigned: PickUnassignedVariable()
- the order of values tried for each variable.

- The choice of the next variable can vary from branch to branch, e.g.,
- under the assignment V1=a we might choose to assign V4 next, while under V1=b we might choose to assign V5 next.

- This 「dynamically」 chosen variable ordering has a tremendous impact on performance.

## Forward Checking

- Forward checkingis an extension of backtracking search that employs a 「modest」 amount of propagation (look ahead).
- When a variable is instantiated we check all constraints that have only one uninstantiatedvariable remaining.
- For that uninstantiatedvariable, we check all of its values, pruning those values that violate the constraint.

## Empirically

- FC often is about 100 times faster than BT
- FC with MRV (minimal remaining values) often 10000 timesfaster.
- But on some problems the speed up can be much greater
- Converts problems that are not solvable to problems that aresolvable

- Still FC is not that powerful.
- Other more powerful forms of constraint propagation are usedin practice

## Generalized Arc Consistency (GAC)

- C(X,Y) is consistent iff for every value of X there is somevalue of Y that satisfies C
- C(V1, V2, V3, . . . , Vn)is GAC wrtViiff for every value ofVi,there are values ofV1, . . . , Vi−1, Vi+1, . . . , Vn that satisfyC
- A constraint is GAC iff it is GAC wrt every variable in its scope
- A CSP is GAC iff all of its constraints are GAC
- Say we find a valuedof variableVi that is not consistent wrta constraint
- i.e., there is no assignments to the other variables that satisfythe constraint whenVi=d
- dis said to be arc inconsistent
- We can remove d from the domain ofVias this value cannotlead to a solution
- Much like Forward Checking, but more powerful
- If d is removed fromCurDom[Vi], it must be the case thatdis arc inconsistent

## GAC algorithm

- We make all constraints GAC at every node of the searchspace.
- Like forward checking, GAC could also be performed beforewe even start to search,i.e., before we assign any variables.
- This is accomplished by removing from the domains of thevariables all arc inconsistent values.

## Enforce GAC

- A support for V=d in constraint C is an assignment A to all ofthe other variables in scope(C) s.t. A U{V=d}satisfies C.
- Smarter implementations keep track of 「supports」 to avoidhaving to search through all possible assignments to the othervariables for a satisfying assignment.
- Rather than search for a satisfying assignment to C containingV=d, we check to see if the current support is still valid: i.e.,all values it assigns still lie in the variable’s current domains
- Also we take advantage that a support for V=d, e.g.{V=d,X=a, Y=b, Z=c}is also a support for X=a, Y=b, and Z=c
- However, finding a support for V=d in constraint C still in theworst case requiresO(2k)work, where k is the arity of C.
- Another key development in practice is that for someconstraints this computation can be done in polynomial time.
- e.g., all-diff(V1, . . . , Vn) we can check ifVi=dhas a supportin the current domains of the other variables in polynomialtime using ideas from graph theory.