CSP与传统搜索不同的是采用因子化表示状态

• 因子化表示为一组变量，变量有自己的值
• 求解问题时，每个变量的值须满足对该变量约束

约束满足问题

可以以三部分定义约束满足问题

• 变量集合X，$\{X1,X2,\cdots,X_n\}$
• 域集合D，表征变量的取值范围，每个变量都需要有与$\{D_1,D_2,\cdots,D_n\}$
• 约束集合C，规定哪些变量取值是允许的

约束可以抽象地表示为

CSP希望对变量进行赋值，不违反约束的赋值是合法赋值，每个变量都被赋值则为完美赋值。CSP的解是合法完美赋值

约束传播

CSP下可以通过约束传播的过程进行推断。选择变量赋值时，需要考虑的合法选项会减少

1. 节点一致性：单个变量的取值在其域中
2. 弧一致性：单个变量的取值满足二元约束

如对于约束“X,Y是整数，并且$Y=X^2$”中，整数是节点一致性，$Y=X^2$是弧一致性

AC3

AC3算法用于进行弧一致性约束，可以描述如下

0. 将所有的弧（两个变量的二元约束）加入队列
1. 从队列中取出弧$(X_i,X_j)$
2. 检查两个变量$X_i,X_j$是否有不满足该约束的取值，若有则删除取值
3. 若2操作使得某些变量的域变小，则将这些变量关联的弧加入队列
4. 回到1循环，直到队列为空

路径一致性3-Consistency

弧一致性只考虑了二元约束，可能并不能很好地约束变量的域。此时需要引入第三个变量通过观测变量的三元推断将二元约束收紧

可以进一步推广到k-Consistency