约束满足问题

约束满足问题（Constraint satisfaction problem，CSPs）是种数学的问题，其定义为一组对象（object），而这些对象需要满足一些限制或条件。CSPs将其问题中的单元（entities）表示成在变数上有限条件的一组同质（homogeneous）的集合，这类问题透过“约束满足方法”来解决。CSPs是人工智能和运筹学的热门主题，因为它们公式中的规律，提供了共同基础来分析、解决很多看似不相关的问题。通常约束满足问题具有高度复杂性（英语：Complexity of constraint satisfaction），需要同时透过启发式搜索和联合搜索（英语：Combinatorial search）的方法，来在合理的时间内解决问题。布尔可满足性问题（SAT），可满足性的理论（英语：Satisfiability modulo theories）（SMT）和回答集程式设计（ASP）可以算是某种程度上的约束满足问题。

以下举例为几个简单的约束满足问题:

• 八皇后问题
• 图着色问题
• 填字游戏、数独及其他一些逻辑益智游戏

这些ASP是BooleanSAT和SMT教学课程的人常会使用的范例。在现实情况下，约束满足问题通常更困难，且难以用简单的范例来表达，例如自动规划（英语：Automated planning and scheduling）和资源配置。

定义

正式来说，约束满足问题定义为一个三元组${\displaystyle \langle X,D,C\rangle }$，其中

${\displaystyle X=\{X_{1},...,X_{n}\}}$是变数的集合，

${\displaystyle D=\{D_{1},...,D_{n}\}}$是各个变数的定义域集合，而

${\displaystyle C=\{C_{1},...,C_{n}\}}$是限制条件的集合。

每个变数${\displaystyle X_{i}}$可以在非空的定义域${\displaystyle D_{i}}$中取出。每个限制条件（Constraint）${\displaystyle C_{j}\in C}$依序对应一对${\displaystyle \langle t_{j},R_{j}\rangle }$，其中${\displaystyle t_{j}\subset X}$是变数的${\displaystyle k}$元组，${\displaystyle R_{j}}$则是在定义域${\displaystyle D_{i}}$中，其对应到的子集合上得到的${\displaystyle k}$元组的关系。变数的定值（evaluation或assignment）是一个函数，其从变数的子集合映射到该变数子集合所对应到的定义域子集合中特定的值组成的集合，也就是

${\displaystyle f:X'\rightarrow V}$其中${\displaystyle X'=\{X_{p_{1}},X_{p_{2}},X_{p_{3}},...,X_{p_{k}}\}\in X,V=\{v_{1},v_{2},v_{3},...,v_{k}\},v_{i}=f(X_{p_{i}})\in D_{p_{i}}}$。

如果${\displaystyle f(X_{p_{1}}),\ldots ,f(X_{p_{k}})\in R_{j}}$，则此定值${\displaystyle f}$满足条件限制${\displaystyle \langle t_{j},R_{j}\rangle }$。

如果一个定值不违反任何的条件限制，我们说这个定值是无矛盾的（consistent）。 如果一个定值包含了所有的变数，我们说这个定值是完备的（complete）。 如果一个定值无矛盾而且完备的，我们说这个定值是一个解（solution），这样的定值就是CSP的解。^[1]

解决方法

定义域有限的约束满足问题通常利用搜索方法来解决。最常用的技术是回溯法（backtracking）、约束传递constraint propagation，以及局部搜索local search的改良。

回溯法是一种递归算法，它保持部分变数的赋值。一开始，所有的变数都还没被赋值。在每一个步骤中，先选取一个变数，并且将所有可能的值依次赋予该变数。对于每一个值，在限制条件下的局部赋值的无矛盾性（consistency）都进行检查。在符合无矛盾（consistency）的情况下，就会递归地往下呼叫。当所有的值都试过，算法则回溯上层。在这个基本回溯算法中，无矛盾性（consistency）被定义为满足所有的条件限制，且这些条件限制的变数已被赋值。若干回溯变数存在。回溯法提高了检查无矛盾性的效率。回跳法可以使在某些在某些情况中，透过回溯”一个以上的变数“，来省去部分的搜寻。约束学习则借由减少新的条件限制，来避免部分的搜寻。可预见性也常常在回溯法中应用，用来去预期选择一个变数或值的影响，因此常常用来预先判定一个子问题什么时候满足或不满足。约束传递（Constraint propagation）技术是用来修饰一个CSP的方法。更精确地说，是一种方法，用来增强一种形式的局部一致性，是一种条件牵连到一组变数或条件限制的一致性。约束传播应用在各个领域。一来，它把问题转化为一个等价但通常是最简单的解决方法。二来，他可以用来验证满足或不满足于问题。一般来说他不保证会发生，但是它总是会发生一些形式的约束传递（Constraint propagation）或某些种类的问题。最有名的惯用的局部一致性是弧协调性，超弧一致性，和路径一致性。最流行的方法是AC-3约束传播算法，该算法可以执行弧的一致性。

局部搜索方法是不完全满足的算法。人们可能找到解决问题的方法，但这方法可能令我们失望。其反复更改变数来改进整个任务，而得以运作。在每一步，要更改少量变数的值，与整体目标数量的增加条件限制以满足的任务。最小冲突算法是局部搜索算法和基于特定CSPs原则。在实践中，局部搜索似乎工作当这些变化也受随机选择。整合搜索和局部搜索被开发了，导致混合算法。

理论

判定问题

CSPs也研究计算复杂性问题和有限模型理论。一个重要的问题是，是否为每一组的关系、套都可视为CSPs选自只使用关系设置不是在p或NP-完全问题。如果这样一个二分法真实可靠，那么CSPs提供已知的最大的一个NP子集，避免NP-intermediate问题，其存在是证明了Ladner's理论在这种假定下P≠NP。Schaefer's二分法理论处理所用变量相关时的情况布尔数学运算符，也就是，对一个定义域大小为2的。最近的一个促进dichotomoy二分定理推广到一个更大的类的事务。^[2]

功能问题

相同的情形存在于功能类别之间，FP和#P。通过一般的Ladner's理论，FP和#P-complete也存在问题如果FP≠#P。在这种决策下，一个#CSP问题被定义为一组关系。每个问题需要输入布尔公式作为输入，任务是计算数字令人满意的工作。这可以进一步推广利用大域大小和附上一个权重，对每一个满意的赋值和计算这些权值的总和。众所周知任何复杂的#CSP权重问题既不是FP也不是#P-hard问题。^[3]

变型

经典的造型约束满足问题定义了一个静态模型，呆板的约束。这个严格的模型的缺点是他很难容易的表现问题^[4]。基于CSP定义的几种修改，提出使该模型广泛适应各种各样的问题。

动态CSPs

动态CSPs^[5]（DCSPs）是有用的，当原有的问题形式以某种方式改变，通常是由于约束集进化，因为要考虑环境^[6]。DCSPs被当做一系列的静态CSPs，每一个都是转变的前一个变量和约束可以添加或删除限制（放松）。信息在初始的配方发现问题可以用来提炼下一个。解决的方法可分为根据信息的方法在转让:

• Oracles:解决之前发现的序列CSPs作为启发式方法指导解决当前CSP从零开始。
• Localrepair:每个CSP计算从解决部分问题之前的修复与Local search。局部搜索不约束。
• Constraintrecording:新的约束是定义在每一阶段的搜索代表学习群决策不一致。在这些约束进行了新的CSP问题。

灵活的CSPs

经典的CSPs处理约束很严格，意味着强制的（每一解决方案必须满足所有问题）并且刻板的（意味着，以至于他们必须被完全满足，否则他们是完全违反了）。灵活的CSPs放宽假设，部分的放宽限制对不遵循的的也一样解决问题。这类似于preference-based planning。一些类型的灵活CSPs包括:

• MAX-CSP，在那里有好些约束允许受侵犯的质量，并通过测量方法多少满意的约束。
• 加权CSP，使每一个MAX-CSP违反约束加权根据预定义的偏好。因此，更重要的是满足约束的优先考虑。
• CSP模糊的约束关系，在这种情况下约束满足是变量的连续函数，从完全满足到完全不满足。

参见

• 约束满足
• 声明式编程
• 规划约束
• 分布式约束满足问题（DisCSP）

参考文献

1. Stuart Jonathan Russell; Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall. 2010: Chapter 6. ISBN 9780136042594.
2. Bodirsky, Manuel; Pinsker, Michael. Schaefer's theorem for graphs. CoRR. 2010,. abs/1011.2894: 2894. Bibcode:2010arXiv1011.2894B. arXiv:1011.2894 .
3. Cai, Jin-Yi; Chen, Xi. Complexity of Counting CSP with Complex Weights. CoRR. 2011,. abs/1111.2384 [2012-04-08]. （原始内容存档于2017-01-17）.
4. Ian Miguel. Dynamic Flexible Constraint Satisfaction and its Application to AI Planning (2001). University of Edinburgh School of Informatics. [2014-05-04]. hdl:1842/326 doi:10.1.1.9.6733. （原始内容存档于2016-03-04） （英语）.
5. Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks In Proc. of AAAI-88, 37-42. (PDF). [2012-04-08]. （原始内容 (PDF)存档于2012-11-17）.
6. Solution reuse in dynamic constraint satisfaction problems （页面存档备份，存于互联网档案馆）, Thomas Schiex

扩展阅读

• Steven Minton, Andy Philips, Mark D. Johnston, Philip Laird. Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems (PDF). Journal of Artificial Intelligence Research. 1993, 58: 161–205.^{[永久失效链接]}

超链接

• CSPTutorial

• Tsang, Edward. Foundations of Constraint Satisfaction. Academic Press. 1993 [2012-04-08]. （原始内容存档于2021-04-23）.ISBN 0-12-701610-4
• Chen, Hubie. A Rendezvous of Logic, Complexity, and Algebra. ACM Computing Surveys (ACM). December 2009, 42 (1): 1–32. doi:10.1145/1592451.1592453.
• Dechter, Rina. Constraint processing. Morgan Kaufmann. 2003 [2012-04-08]. （原始内容存档于2021-04-25）.ISBN 1-55860-890-7
• Apt, Krzysztof. Principles of constraint programming. Cambridge University Press. 2003.ISBN 0-521-82583-0
• Lecoutre, Christophe. Constraint Networks: Techniques and Algorithms. ISTE/Wiley. 2009 [2012-04-08]. （原始内容存档于2017-11-07）.ISBN 978-1-84821-106-3
• TomásFeder，Constraintsatisfaction:apersonalperspective（页面存档备份，存于互联网档案馆），manuscript.
• Constraintsarchive
• ForcedSatisfiableCSPBenchmarksofModelRB（页面存档备份，存于互联网档案馆）
• Benchmarks--XMLrepresentationofCSPinstances
• DynamicFlexibleConstraintSatisfactionandItsApplicationtoAIPlanning，IanMiguel-slides.
• ConstraintPropagation-DissertationbyGuidoTackgivingagoodsurveyoftheoryandimplementationissues