约束补偿问题（CSPs）是种数学的问题，其定义为一组物件(object)，而这些物件需要满足一些限制或条件。 CSPs将其问题中的单元(entities)表示成在变数上有限条件的一组同质(homogeneous)的集合, 这类问题透过"约束补偿方法"来解决。
- Situation can be described by a set of variables
- Constraint is a condition the variables must meet
- Problem: find assignments of values satisfying all constraints
- The constraint satisfaction problem (CSP) consists in finding a solution for a constraint network
Example: Eight queens puzzle
Binary constraint network
A constraint network is a triple⟨V,D,C⟩.
V: a finite set of variables
D: a set of finite or infinite sets considered to be the domains of every variable.
C:a set of binary relations
E.g. V = {a,b}. Suppose Da = {1,...,10} and Db = {8,...,20}. If we require a > b then Ca,b is the set {(9, 8), (10, 8), (10, 9)}.
1.Extension to non-binary constraints is simple.
2.SAT is the special case where all domains have just 2 values
Consistency of a partial assignment
if a is a partial assignment, then there are variables u, v in V and a constraint Cu,v in C such that a(u) and a(v) are defined, and (a(v), a(u)) ∈/ Cu,v
In that case, a violates the constraint Cu,v
So, the a is inconsistent.
1.A partial assignment a can be extended to a solution(A consistent total assignment is a solution) if there is a solution which agrees with a wherever a is defined.
2.Not every consistent partial assignment can be extended to a solution.
Pure Backtracking(try to find a solution)
Definition:Recursively instantiate variables one by one, backing up out of a search branch if the partial assignment is inconsistent.
Search: Systematic enumeration of partial assignments
— If a complete assignment is found, that’s a solution
— If the search space is exhausted, there are no [more] solutions
Backtracking: Pruning of inconsistent partial assignments (and all their extensions).
Inference: Reasoning about a partial assignment, to tighten constraints and reduce domains for its extensions.
There is a tradeoff: reduction in number of search nodes vs runtime needed for inference
Time complexity: O(n^k) n is the number of value choice and k is the number of variables.
Space complexity: O(k)
Advantages:
1.Very simple to implement
2.Very fast (per node of the search tree)
3.Complete (always gives a decision)
Disadvantages:
1.Does no reasoning except detecting actual inconsistency
2.Cannot look further ahead than the current state
Improvement
To avoid enumerating many inconsistent (partial) assignments by detecting them early
