约束满足问题可以定义为一个三元组<X,D,C>的形式,其中:
- X={X_1, X_2, ... ,X_n}是变数的集合
- D={D_1, D_2, ... ,D_n}是各个变数的定义域集合
- C={C_1, C_2, ... ,C_n}是限制条件的集合。
每个变数X_i可以在非空的定义域D_i中取出。每个限制条件(Constraint)C_j依序对应一对<t_j,R_j>,其中t_j是n-tuple的变数， 则是在定义域D_i中，其对应到的子集合上得到的n 维的关系。 变数的评估(evaluation)是一个函数，其从变数的子集合映射到一组特定的集合，集合内为定义域的子集合所对应到的值，也就是
如果满足：
则此评估(evaluation)ƒ满足条件限制：
常见的约束满足问题有：
- 八皇后问题
- 图着色问题
- 填字游戏问题
- 哈密顿回路问题
[描述来源：Wikipedia；URL：https://en.wikipedia.org/wiki/Constraint_satisfaction_problem]
2. 发展历史
描述
约束满足问题的求解技术主要分为两部分：推理和搜索。推理是通过变量消元、树分解、相容性技术（也称约束传播算法）等方法将问题规模简化，从而使问题更容易求解，其中相容性技术是约束推理的核心技术。1980年，提出了结合弧相容技术的回溯算法Forward checking来获得CSP的解。1989年，单弧相容被提出来，1991年，结合弧相容技术的回溯算法Maintain arc consistency被提出。同一年，P.Cheeseman等人指出随机中很多难解实例在相变点附近找到。 2011年，Fan等人提出了一个随机的约束选择问题：k-CSP。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1980 | 结合弧相容技术的回溯算法Forward checking来获得CSP的解 | Haralick, R. M., & Elliott, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial intelligence, 14(3), 263-313. |
| 1989 | 利用单弧相容来求解CSP问题 | Dechter, R., & Pearl, J. (1989). Tree clustering for constraint networks. Artificial Intelligence, 38(3), 353-366. |
| 1991 | 结合弧相容技术的回溯算法Maintain arc consistency来获得CSP的解 | Bessiere, C. (1991, July). Arc-Consistency in Dynamic Constraint Satisfaction Problems. In AAAI (Vol. 91, pp. 221-226). |
| 1991 | P.Cheeseman等人指出随机中很多难解实例在相变点附近找到 | Cheeseman, P. C., Kanefsky, B., & Taylor, W. M. (1991, August). Where the really hard problems are. In IJCAI (Vol. 91, pp. 331-340). |
| 2011 | 提出了一个随机的约束选择问题：k-CSP | Fan, Y., & Shen, J. (2011). On the phase transitions of random k-constraint satisfaction problems. Artificial Intelligence, 175(3-4), 914-927. |
3. 发展分析
未来发展方向
- 基于自适应的CSP算法
- 选择更适合的算法来增强自适应强度
Contributor: Yilin Pan