1.3.1　约束满足问题

调度问题实际上可视为一个约束满足问题（Constraint Satisfaction Problem，CSP），包括：

●一组变量

●每个变量的定义域

●一组约束

我们可以使用下面的例子来理解CSP。

例（配送机器人）：配送机器人配送物品a、b、c、d、e，并且每次配送可在t1、t2、t3、t4四个时刻里面的某个时间发生。用变量A、B、C、D、E分别表示配送物品a、b、c、d、e的时刻。变量A、B、C、D、E的定义域为

dom（A）={t1，t2，t3，t4}

dom（B）={t1，t2，t3，t4}

dom（C）={t1，t2，t3，t4}

dom（D）={t1，t2，t3，t4}

dom（E）={t1，t2，t3，t4}

假设我们需要满足的约束如下：

{（B≠1），（C≠4），（A=D），（E<B），（E<D），（C<A），（B≠C），（A≠E）}

练习：给定上述设置，请回答下列问题：

（a）问题有模型吗？

（b）如果有，请给出一个模型。

（c）我们可以设计多少个模型？

（d）请给出所有模型。

（e）如果提供合适的性能度量，最好的模型是什么？一个可能的性能度量是需求时刻的最小数目。

赋值空间D表示所有赋值的集合。在配送机器人例子中，赋值空间是

D={（A=1，B=1，C=1，D=1），（A=1，B=1，C=1，D=2），…，…，（A=4，B=4，C=4，D=4）}

一个有限CSP直观上可通过穷举生成与测试算法来求解。以配送机器人为例，需要测试|D|=45=1024种不同的任务，并会随配送物品数目而呈指数增长，显然，在计算上不具有可伸缩性。如果m各变量定义域的每个集合大小为d，则D有dm个元素需要测试。如果存在c个约束，则穷举测试的总数为O（cdm），很容易就变为不可计算的。因此，需要一种智能方法。

通常，最直接的方法是进行有效的搜索来解决问题，而搜索通常被认为是人工智能的一项核心技术。特别地，由线性约束函数组成的CSP形成了一类线性规划（LP）问题。

1939年，俄罗斯数学家列奥尼德·康托罗维奇（Leonid Kantorovich）首先系统地研究了线性规划。对于线性规划问题，约束必须是构成凸集的线性不等式，目标函数也必须是线性的。线性规划的时间复杂度是变量数的多项式。线性规划可能是最广泛研究和使用的一类优化问题。它是更一般的凸优化问题的一个特例，其中的约束区域是任意凸区域，目标函数在约束区域内也是凸的。在一定条件下，即使有上千个变量，凸优化问题也是多项式可解的，并在实践中也是可行的。

例（地图着色）：美国大陆有48个州。我们想给每个州涂一种颜色，并且相邻州必须使用不同的颜色。这也是一个CSP约束满足问题。

着色地图问题有一个更深层次的版本，即绘制任何地图的最小颜色数是多少，这在图论中被称为四色问题。图论为理解许多与机器人相关的人工智能问题提供了一种有用的方式。