CSP 是 Constraint Satisfaction Problem 的缩写, 目的是找到符合约束条件的一组解.

相比搜索问题, CSP 的 状态(state) 是由变量 及其定义域 定义的, 目标状态(goal test) 是一组约束, 这些约束确定了变量的取值组合. 主要思想通过寻找违反约束的变量或值组合来减少搜索空间的大小, 即做剪枝.

变量分为离散变量和连续变量, 离散变量的取值可以是有限集(比如 boolean)或者无限集(比如整数集或字符串). 通过约束的变量个数对约束进行分类, 包括 unary, binary以及 higher-order. 下面会更多地介绍 binary-CSP, 因为此时可以很容易地用图来描述变量之间的关系.

作为搜索问题的子集, 解决 CSP 的最简单的方式当然是 DFS, 或者说回溯(backtracking), 此时不关注变量赋值的顺序, 即认为变量赋值这一操作是可交换的.

设变量 的值域为 , 初始情况下默认 . 以地图染色为例子, 设 , 相邻的两块地图颜色需要不同, 下面是原图和抽象出来的 graph.

提高回溯的效率

搜索过程中需要枚举不同的变量以及变量不同的取值, 枚举的顺序实际上对效率有较大的影响, 对于下个状态选择哪个变量赋值, 给选择的变量赋哪个值, 以及能否更早地剪枝以避免不必要的搜索, 采用以下策略.

对于变量:

• Most constrained variable. 即选择"被约束得最厉害的"那个变量, 或者说合法(指不违反约束)取值数目最小的变量. 比如下图在涂过绿色之后, 城市 SA 只剩蓝色这一种选择, 那么优先给 SA 涂上蓝色.

• Most constraining variable. 选择变量之后, 剩下的变量"被约束得最厉害", 即使剩下的变量的合法取值变得最少. 这样做的是因为所有的变量都必须被赋值, 可以更早地搜索到不成立的情形. 比如在初始状态, 城市 SA 是最好的选择, 因为 SA 的颜色确定之后, WA, NT, Q, NSW, V 的合法取值均减一, 是减少的最多的.

对于变量的取值:

• Least constraining value. 选择的值对剩余变量的合法取值的减少应该最小. 这样做可以减少对变量取值的尝试, 减少不必要的分支. 比如下面的情况, 应优先给 Q 涂红色而不是蓝色, 否则会导致 SA 没有合法的颜色可选.

Forward Checking

Forward Checking 是一种进一步减少搜索树规模的技术, 在给某个变量赋值之后, 在进行下一步搜索之前, 可以根据约束先一步减少未赋值变量合法取值的数量, 这称为一次 check, 若 check 以后出现了仅剩一种取值的变量 , 那么可以根据 这唯一的取值继续根据约束减少剩余变量的合法取值的数量, 这称为传播(propagation).

需要注意 forward checking propagation 并不能提前检测到不成立的情形, 当传播完毕后, 搜索还需要继续进行才能确定是否要终止这一分支的搜索.

Arc Consistency

弧一致性检验主要是在 binary-CSP 中应用, 对于一个 binary-CSP, 以变量为顶点, 约束为弧, 构造有向图 , 这里 相当于变量数, 相当于约束数. 对于其中的两个变量 , 若 出现在同一约束中则 , 那么弧 是一致的当且仅当对于任意 都存在合法的 可以取到, 如果某个 使得所有 都不能取到, 那么这个 就没必要再选了, 可以直接删去, 此时 的取值丢失了一个值后, 需要重新检查 的邻居 . 当存在不一致的弧时, 就说明当前状态已经不满足约束, 是一个失败的状态, 算法 AC-3 可以用来找到一个状态是否存在不一致的弧.

这个算法维护一个队列存弧, 每次取队首元素 判断根据当前状态是否可以修改 的取值 , 如果修改了且 不存在合法取值就意味着找到了不一致的弧, 否则就要重新check 与其邻居的弧一致性, 因此就将弧 加到队列中. 根据当前状态以及弧 修改 的取值, 只需要删去 满足 都不满足约束, 如果不存在这样的 , 则不做任何修改.

对于任意两个变量, 检查它们的弧一致性需要枚举两个变量的所有取值, 这一步骤的复杂度为 , 于是 AC-3算法的复杂度为 .

相比 forward checking, arc consistency 可以更早地检测到当前分支的失败; 同时AC-3算法无法发现所有的不一致的弧, 比如下图的情况:

这显然是一种不合法的情况, 不管怎么取值都会有两个相邻的取到相邻的颜色, 但是弧一致性检验只能两两之间检验.

-consistency

如果一个 CSP 问题, 对于它的任意 个变量任意地合法赋值, 第 个变量都存在合法的值可以被赋予, 那么就称该 CSP 问题是 -consistent 的. 显然 -consisteny 是 node consistency, -consistency 是 arc consistency.

Tree-structured CSPs

当上文的 binary-CSP 对应的图 是一棵树, 那么该 CSP 可以在 的时间内解决, 而一般的 CSP 的最坏时间复杂度为 . 这是一个 DP 算法:

随机选择一个结点作为根节点, 按照拓扑排序得到一个节点序列保证父节点在子节点之前, 接着倒序遍历得到的序列, 对 进行弧一致性检验, 删去一些值, 那么再正序遍历, 给每一个结点 赋一个与其父节点 的值相容的值即可, 这是一定可以做到的, 因为前面做过弧一致性检验后保证了对于父节点的任意一个取值, 子结点至少有一个合法取值.

由于大部分图不是树形结构, 但是对于比较接近树结构的图, 我们可以在图中找到最少的点(这是NPC的), 删去这些点之后使得剩下的子图成为一颗树(比如删去城市 SA), 那么就可以用上面的算法来解决, 对于删去的点直接枚举每个点的所有取值即可, 设删去的点的数目为 , 那么复杂度为 , 我们希望 比较小.

Tree decomposition

为了使用 tree-structured CSPs 的复杂度较低的算法, 除了上面的删点手段, 还可以使用 Tree decomposition, 即组合若干相邻节点称为一个"大结点"(meganode), 如下图所示, 同一个结点可以在不同的"大节点"中出现, 使 meganode 之间成为一棵树, 且要保证其赋值的一致性.

定义树宽为 , 当树宽为 时原图为树.

在 中, 若已知 , 则在 tree decomposition 得到的树中, 所在的 meganode 的数量为 且这些 megenode 恰好可以连成一条 path.

下面是另一个例子:

处理的时候先处理每个 meganode, 再使用 tree-structured CSPs 的算法处理整棵树即可. 那么复杂度为 , 对任意图, 找到它的最小树宽的问题是 NPC 的, 可以用启发式算法找到一个相对小的.

Local Search for CSPs

对于一个 CSP, 可以随机给一种赋值方案, 这大概率会有违反约束的情况, local search 指的是通过不断调整不同变量的值来消除违反约束的部分, 最后得到一个可行解.

习题

6.4 Give precise formulations for each of the following as constraint satisfaction problems:

1. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.

2. Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.

3. Hamiltonian tour: given a network of cities connected by roads, choose an order to visit all cities in a country without repeating any.

Find a permutation of such that .

6.6 Show how a single ternary constraint such as “” can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains. (Hint: Consider a new variable that takes on values that are pairs of other values, and consider constraints such as “X is the first element of the pair Y .”) Next, show how constraints with more than three variables can be treated similarly. Finally, show how unary constraints can be eliminated by altering the domains of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.

这个问题最终要求证明任意的 CSP 问题都可以转化为 binary-CSP 问题.

根据 hint, 令 , 那么约束 可以转化为如下的三个 binary constraint: 对于更多变量的约束, 比如 , 当表达式为线性或者二次型时还能采用上述方法, 但是如果约束比较复杂, 还能怎么办呢?

6.13 AC-3 puts back on the queue every arc whenever any value is deleted from the domain of , even if each value of is consistent with several remaining values of . Suppose that, for every arc , we keep track of the number of remaining values of that are consistent with each value of . Explain how to update these numbers efficiently and hence show that arc consistency can be enforced in total time .

6.14 The TREE-CSP-SOLVER (Figure 6.10) makes arcs consistent starting at the leaves and working backwards towards the root. Why does it do that? What would happen if it went in the opposite direction?

弧一致性检验要求当某个结点的合法取值被删去之后要 recheck 其邻居, 对于树形结构的 CSP, 每次删去的都是父节点的取值, 倒序遍历时, 父节点的祖先还没有被更新过, 可以在遍历的过程中一次更新, 而其儿子不需要再更新; 如果正序遍历, 那么删去某个父节点的值后, 还要再检查该父节点的父亲结点, 这个检查有可能会继续传播直到根节点, 造成了大量的开销. 因此倒序遍历保证了每个结点只 check 了一次.