前言
昨天在吉林大学经信报告厅听了孙吉贵教授的一次题为“基于约束的计算——约束程序设计”的讲座。孙老和蔼可亲，平易近人，精神矍铄，说话言简意赅，逻辑清晰，给我留下了深刻的印象。
由于时间有限，孙教授只能是以介绍为主，辅以实例，因此，我也只能感受到约束程序设计的奇妙，却无法理解它的原理和很多细节。这篇文章也是我根据笔记整理出来的，还有一部分是我自己的理解，希望和原意没有差太多。
思想
约束程序设计，英文为Constraint Programming，缩写CP。
在解释CP时，孙教授讲了这样一件真事。在199x年（Sorry，我忘了），孙教授第一次出国开会，地点是德国的一个小镇。会议结束后，他需要定火车票，但又不知道该怎么买，于是便到小镇的火车站的咨询处咨询，孙教授告诉工作人员他需要在什么时间之前离开，什么时间之前到达，并且表示希望省钱，于是工作人员将这一系列约束输入计算机，计算机便打印出了一张表格，详细的列出了最省钱的乘车路线。
于是我们看到，约束程序是关于约束的计算系统，它的输入是一组约束条件和需要求解的若干问题，输出问题的解决方案。至于具体解决问题的算法等都是CP语言的基本功能。程序员所要面对的，就是如何把问题描述为一组约束构成的模型，而描述的语言可以很接近自然语言。如果把问题的解决方案也看作是一种约束，那么问题的求解就是求得一个或若干个约束，他们每一个都是这一组给定约束的充分条件，也就是说，求得的这些约束，满足这组给定的约束。于是，CP便可以称为面向约束的程序设计方法。
优点
约束的表达是说明性的，实现的细节是由语言提供，同一组约束可以解决不止一个问题。
论域
每一种程序设计方法都有它擅长处理的领域。CP的应用范围决定于约束的论域，主要有以下5种：
- 布尔论域：如SAT问题。
- 树论域：如Herbrand项。
- 实数论域：如代数方程，线性规划。
- 有穷集合论域：如组合调度。
- 序列论域：如DNA序列。
可以看到，CP所面对的问题，绝大多数都是离散的。
在其论域范围之内，我们可以把一个问题的描述看作是一组约束。但是问题并不是这样简单。问题有三种：
- 结构化问题：可以建立起很好的数学模型。
- 非结构化问题：没有数学模型，没有精确的数学表达式，这样的问题通常还要求与用户交互。
- 半结构化问题：例如很多NP完全问题。
应该说，对于第一类问题，CP可以做的非常好，但是另外两类问题还属世界难题，目前CP能做的还很有限，毕竟CP还很年轻。
也许还会有人说，对于很多NP问题，已经有了很优化的算法可以解决了。然而，这些算法都是专用算法，只能解决一种问题，而CP要做的是提供一种通用的方法，以解决尽可能多的问题。尽管它不可能解决所有的问题，但至少可以解决一部分问题。
约束求解器
约束求解器中定义各种论域上的基本约束及其高效的求解过程，紧密嵌入到宿主语言中，形成约束程序设计语言。程序员能根据基本的约束来定义它们所处理的问题和特定的约束。
那么什么是约束呢？约束是问题的一部分限定描述信息，没有方向性，可以动态添加，通常不具有独立性。
CP语言分类
CP主要有三种类型：
- 约束逻辑程序设计语言CLP：如CLP(R)和Prolog-III 。
- 嵌入过程性语言的约束程序设计语言：如ILOG Solver 。
- 并发约束程序设计语言CC：如cc(fd)。
三种类型的约束程序中，约束逻辑程序的语义目前阶段研究的比较充分。 1998年，J.Jaffar等人第一次给出了较完整的CLP语义。CLP语义是逻辑程序设计语义的推广。 CLP方案依赖于参数C（约束论域），CLP(C)实际上是是一族语言，给定一个C就得到一个具体的CLP(C)语言。
很多种CP语言方案采用紧密或松散的嵌入到面向过程或对象的语言中。
CP建模
约束程序设计应用的关键在于问题建模，而不是象过程性语言那样需要用户把许多精力用于解决问题的具体方法的编程。
所谓问题建模是指将应用问题的参数用变量表示，问题中各个对象之间的相互关系用约束来表达，并将这种从应用问题中抽象出来的“高级约束”翻译为CP的约束求解器所支持的“低级的”基本约束。
目前的成绩
孙教授所在课题组于1998年开始从事约束程序设计方向的研究和开发。是国内最先从事约束程序研究的三个单位之一。目前已经设计实现了国内第一个嵌入到过程语言的约束程序系统“明月1.0”（C++）。
孙教授还展示了使用该系统解决N皇后问题的效果。该系统在测试范围内（问题规模1-400）都能求解，运行速度也大都在2000毫秒以内，最高4000毫秒。相比较之下，国外的同样功能的系统cream，在测试中有一半无法求解，且运行时间普遍在4000毫秒，最高竟达13000毫秒。
对于代码我也进行了统计。解决该问题，总共用了22行，5行是问题求解，12行建模（其余为main()函数1行，大括号4行）。
后记
约束程序设计的发展只有10多年的时间，很多研究还都是刚刚起步，有很大的发展潜力。目前，国内似乎对CP认识不多，资料很少，所以，我觉得CP是一个很有挑战性的研究方向，而且，1996年ACM在庆祝成立50周年大会上，曾指出约束程序设计是21世纪计算机科学19个具有战略意义的研究方向之一。