约束满足问题

数学问题

约束满足问题（CSPs）是种数学的问题，其定义为一组对象(object)，而这些对象需要满足一些限制或条件。

简介

CSPs将其问题中的单元(entities)表示成在变量上有限条件的一组同质复杂性, 需要同时透过启发式搜索和联合搜索的方法，来在合理的时间内解决问题。布尔可满足性问题 (SAT), 可满足性的理论 (SMT)和回答集程序设计 (ASP) 可以算是某种程度上的约束满足问题。

定义

正式来说，约束满足问题定义为一个三元组，其中

是变量的集合,

是各个变量的定义域集合,而

是限制条件的集合。

每个变量可以在非空的定义域中取出。每个限制条件(Constraint) 依序对应一对，其中则是在定义域中，其对应到的子集合上得到的维的关系。变量的评估(evaluation)是一个函数，其从变量的子集合映射到一组特定的集合，集合内为定义域的子集合所对应到的值，也就是

如果，则此评估(evaluation) f满足条件限制。

如果一个评估不违反任何的条件限制，我们说这个评估是无矛盾的(consistent)。如果一个评估包含了所有的变量，我们说这个评估是完备的(complete)。如果一个评估无矛盾而且完备的，我们说这个评估是一个解(solution)，这样的评估就会用来解决CSP。

CSPs的解决方法

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

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

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

CSPs的理论方面

判定问题

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

功能问题

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

CSPs的变型

动态CSPs

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

灵活的CSPs

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省