约束逻辑程序设计

在我们对前向链接的讨论中（第9.3节），我们显示了约束满足问题（CSP）如何被编码成确定子句。标准的Prolog用和图5.3给出的回溯算法完全一样的方法求解这类问题。

因为回溯枚举了变量的域，它只在有限域CSP中可行。在Prolog术语中，对任何具有未绑定变量的目标来说，它的解的数量一定是有限的。（例如，目标 diff(q,sa)，意思是昆士兰和南澳大利亚的颜色应该不一样，如果允许使用3种颜色，则有6组解）。无限域的CSP——例如具有整数或实数的变量——需要完全不同的算法，比如界限传播或线性规划。

如果3个数满足三角不等式，则下列子句成功：

triangle(X,Y,Z) :-

X>=0, Y>=0, Z>=0, X+Y>=Z, Y+Z>=X, X+Z>=Y

如果我们对 Prolog 提出查询 triangle(3,4,5)，则过程很顺利。另一方面，如果我们查询triangle(3,4,Z)，将无解，因为Prolog无法处理子目标Z>=0。难点在于Prolog中的变量必须处于两个状态之一：未绑定或绑定于某个特定项。

将某个变量与一个特定项绑定可以视为约束的极端形式，即等式约束。约束逻辑程序设计（Constraint Logic Programming，CLP）允许变量被约束而不是被绑定。约束逻辑程序的解是查询变量上最特定的约束集合，这个集合可以根据知识库推导出来。例如，查询triangle(3,4,Z)的解是约束7>=Z>=1。标准逻辑程序设计只是CLP的一个特例，其中解约束必须是等式约束——也就是绑定。

CLP系统结合了各种不同的约束求解算法来处理语言中允许的约束。例如，允许实值变量的线性不等式的系统在求解这些约束时可能需要包含一个线性规划算法。CLP系统还采用更灵活的方法来求解标准逻辑程序设计查询。例如，它们不使用深度优先、从左到右的回溯，而可能采用第五章中讨论的任何更加有效的算法，包括启发式合取排序、后向跳转、割集调整等等。CLP系统因此将约束满足算法、逻辑程序设计和演绎数据库的元素组合起来。

CLP系统还可以利用第五章中描述的各种CSP搜索优化技术，诸如变量和价值排序、前向校验和智能回溯。一些系统被定义为允许程序员对推理的搜索次序有更多的控制。例如，MRS语言（Genesereth和 Smith，1981；罗素，1985）允许程序员编写元规则以决定首先搜索哪个合取子句。用户可以编写一条规则，规定必须首先搜索具有最少变量的目标或者对特殊谓词写出领域特定的规则。