约束满足问题

5.1 约束满足问题

形式化地说，约束满足问题（或缩写为 CSP）是由一个变量集合：X1，X2，…，Xn，和一个约束集合：C1，C2，…，Cm定义的。每个变量Xi都有一个非空的可能值域Di。每个约束Ci包括一些变量的子集，并指定了这些子集的值之间允许进行的合并。问题的一个状态是由对一些或全部变量的一个赋值定义的，{Xi= vi, Xj= vj, …}。一个不违反任何约束条件的赋值称作相容的或者合法的赋值。一个完全赋值是每个变量都参与的赋值，而 CSP 问题的解是满足所有约束的完全赋值。某些 CSP 问题还要求问题的解能使目标函数最大化。

那么这些意味着什么？假设已经厌倦了罗马尼亚，我们正在看一张如图5.1（a）所示的澳大利亚地图，显示出其中的每个状态和区域，我们的任务是对每个区域染上红色、绿色或者蓝色，使得没有相邻的区域颜色相同。为了将这个任务形式化为CSP，我们把图中的区域定义为变量：WA，N T，Q， NSW，V，SA和T。每个变量的值域是集合{red（红色），green（绿色），blue（蓝色）}。约束是要求相邻的区域染成不同的颜色；例如变量WA和NT的允许组合为：

{(red, green), (red, blue), (green, red), (green, blue), (blue, red), (blue, green)}

（约束也可以更简洁地表示为不等式WA ≠ NT，倘若约束满足算法有某种途径来评价这样的表达式。）这个问题有很多可能的解，诸如：

{WA = red，NT = green，Q = red，NSW = green，V = red，SA = blue，T = red}。

把CSP可视化地表示为约束图是有用的，如图5.1（b）所示。图中的节点对应于问题的变量，弧对应于问题的约束。

将问题当作CSP对待有一些重要的好处。因为CSP问题中的状态表示是符合一个标准模式的——即赋了值的变量集合——后继函数和目标测试能够以适用于所有CSP的普遍方式写出。而且，我们可以发展出有效的、普遍的启发式，这样的启发式不需要附加的领域特定的专门技术。最后，约束图的结构可以用来简化求解过程，在某些情况下会使复杂度呈指数级下降。CSP问题的表示是本书讨论的一系列表示中的第一个也是最简单的。

图5.1 （a）澳大利亚主要的州和地方行政区。对此地图染色可以视为一个约束满足问题。目标是对每个区域分配颜色，使得相邻的区域不同色。（b）表示地图染色问题的约束图

很容易看出，CSP问题可以像标准搜索问题一样给出如下的增量形式化：

初始状态：空的赋值{}，其中所有的变量都是未赋值的。

后继函数：可以给任何未赋值的变量赋一个值，倘若该值和先前赋值的变量不冲突。

目标测试：检验当前的赋值是否完全。

路径耗散：每一步的耗散都是常数（例如1）。

每个解必须是一个完全的赋值，因此如果有n个变量，那么解出现的深度为n。此外，搜索树只扩展到深度 n。由于这些原因，CSP 问题经常用深度优先搜索求解。（参见第 5.2 节。）它也是与到达解的路径无关的情况。因此，我们也可以用完全状态形式化，其中的每个状态是一个满足或不满足约束条件的完全赋值。局部搜索比较适用于这种形式化。（参见第5.3节。）

最简单的一种CSP问题涉及的变量是离散的，并且属于有限值域。地图染色问题就是这种问题。第三章中描述的八皇后问题也可以视为有限值域的CSP，其中变量Q1，…，Q8是每个皇后在列1，…， 8中的位置，每个变量的值域是{1，2，3，4，5，6，7，8}。如果CSP问题的任何一个变量的最大值域大小为d，那么可能的完全赋值的数量为O(dn)——也就是，变量个数的指数级。有限值域CSP问题包括布尔CSP问题，它的变量的取值可以是true（真）或false（假）。特殊情况下，布尔CSP包括一些 NP 完全问题，诸如 3SAT 问题。（参见第七章。）因此，在最坏情况下，我们不会期望在低于指数级复杂度的时间内解决有限值域 CSP 问题。不过在许多实际应用中，通用 CSP 算法可以求解问题的数量级大于通过我们在第三章中见过的通用搜索算法可求解的问题。

离散的变量也可以有无限值域——例如，整数集合或者字符串集合。例如，在日历上安排建筑作业，每个作业的开始日期是一个变量，可能的取值是从当前的日期开始计数的整数天数。用无限值域，不再可能通过枚举所有可能取值的组合来描述约束条件了。替代地，必须使用约束语言。例如，如果Job1用五天完成，而且必须在Job3开始之前完成，那么我们就需要用到代数不等式的约束语言，诸如StartJob1+5≤StartJob3。也不再可能通过枚举所有可能的赋值来求解，因为不同的赋值有无限多。对于整数变量的线性约束——也就是，诸如刚刚给出的约束，其中每个变量都只以线性形式出现——存在特殊的求解算法（我们在这里不讨论）。可以证明没有算法能够求解一般的整数变量的非线性约束问题。在某些情况下，我们可以简单地通过限制所有变量的值把整数约束问题简化为有限值域问题。例如，在调度问题中，我们可以设置一个等于要安排的全部作业总长度的上界。

连续值域的约束满足问题在现实世界是十分常见的，并在运筹学领域中有很广泛的研究。例如在哈勃太空望远镜上的实验日程安排要求非常精确的观测时间选择；每次观测的开始、结束时间和机动时间都是连续值变量，它们必须遵守许多天文的、优先权的和电力的约束。最著名的一类连续值域CSP是线性规划问题，其中约束必须是构成一个凸多边形的一组线性不等式。线性规划问题可以在变量个数的多项式时间内求解。具有不同类型的约束和目标函数的问题——二次规划、二阶二次曲线规划，等等——也被研究过。

除了考察出现在CSP问题中的变量的种类，考察约束的类型也是有用的。最简单的类型是一元约束，它只限制单个变量的取值。例如，可能出现这样的情况：南澳大利亚人（South Australian）非常不喜欢绿色。仅仅通过对变量相应的值域进行预处理，删除破坏约束的值，就可以消除一元约束。一个二元约束与两个变量有关。例如，SA ≠ NSW就是一个二元约束。二元CSP只包含二元约束；它可以表示为约束图，如图5.1（b）。

高阶约束涉及三个或更多的变量。一个熟悉的例子是密码算术游戏。（见图5.2（a）。）密码算术游戏中通常每个字母都表示一个不同的数字。在图5.2（a）所示的情况下，这将表示为一个六变量约束Alldiff (F, T, U, W, R, O)。替代地，它也可以用诸如F ≠ T的二元约束的集合表示。游戏的四列算式的附加约束也涉及多个变量，如下所示：

O+O=R+10⋅X1

X1+W+W=U+10⋅X2

X2+T+T=O+10⋅X3

X3= F

其中X1，X2，X3是表示每一列进位（0或1）的辅助变量。高阶约束可以用约束超图表示，诸如图5.2 （b）所示。目光敏锐的读者会注意到，Alldiff 约束可以分解为二元约束——F ≠ T，F ≠ U，等等。实际上，如习题5.11要求你证明的那样，如果引入足够多的辅助变量，每个高阶的、有限值域的约束都可以简化为一个二元约束集合。因此，在本章中，我们只处理二元约束问题。

图5.2 （a）一个密码算术游戏。每个字母表示一个不同的数字；目标是找到能使加法式子成立的代替字母的数字，附加约束是最前面的数字不能是0。（b）密码算术游戏的约束超图，表示了Alldiff约束和每列相加的约束。每个约束在图中用方块表示，连接到它所约束的变量

迄今为止我们已经描述过的约束都是绝对约束，任何违反规则的都排除在解之外。然而许多现实世界的CSP包含偏好约束，指出哪些解是更偏好的。例如，在一个大学课程时间表问题中，X教授可能偏好在上午授课，而Y教授偏好在下午授课。X教授在下午2点授课的时间表虽然是一个解（除非X 教授正好是系主任），但不是最优解。偏好约束通常被计入个体变量赋值的耗散——例如，分配给X教授下午时段在总体目标函数中需要消耗2点，而上午时段只需要消耗1点。用这种形式化，有偏好约束的CSP问题可以用基于路径的或局部的最优搜索方法求解。我们在本章中不进一步讨论这样的CSP问题，但我们会在参考文献与注释一节里提供一些这方面的线索。