人工智能（五）

12 Sep 2019 5205字 18分
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。

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.

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

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.

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

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 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.

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

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

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.

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.