约束补偿问题

维基百科,自由的百科全书
跳转至: 导航搜索

约束补偿问题(CSP)是数学问题,定义为一组状态必须满足于若干约束或限制的目标。 CPSs描绘问题实体,在一个问题中作为均匀限制约束之上的变量, 能够较好地解决了约束补偿 的方法。CSPs热门的研究主题是人工智能运筹学, 因为在他们的公式规律提供了一个公共的基础上分析问题、解决问题的许多不相干的组合。 CSPs经常表现出高复杂性, 需要结合启发式搜索联合搜索 方法来解决的一个合理的时间问题。 布尔可满足性问题 (SAT), ,可满足性的理论 (SMT)和回答集编程 (ASP) 大致可以认为是某些形式的约束补偿问题。 简单的问题的例子可以转化为一个约束补偿问题:

实例证明上述通常提供的ASP教程,布尔SAT和SMT的人。在一般情况下,约束问题会变得更加困难,并不得表述在这些简单的系统里

形式的定义[编辑]

形式上, 约束满足问题定义为一个三元组\langle X,D,C \rangle,这里 X 是一组变量, D值域, C 是一个约束组。每个约束依次对应一对\langle t,R \rangle(通常表现为矩阵形式), tn-tuple 变量R 是一个与D有关的n-ary 维变量。 评估是一个函数的变量集合中变量的领域的值, v:X \rightarrow D. 评估v 满足约束\langle (x_1,\ldots,x_n),R \rangle 如果 (v(x_1),\ldots,v(x_n)) \in R.一个解决方案是满足所有的限制因素的评价。

CSPs的解决方案[编辑]

确定域上的限制约束问题是用一种典型的搜索方法来解决的。 最常用的是变量回溯技术,约束传播,和局部搜索。回溯法 是一种递归算法,它能够保持局部变量的赋值,一开始,所有的变量都未赋值,被选择的变量,在每一步所有可能的值轮流赋给该变量。对于每一个值,在约束下的局部赋值的一致性,需要核对。以防一致性递归调用执行,当所有的值都试过,算法执行完毕。在这个基本回溯算法中,一致性被定义为满足所有的限制约束,这些限制约束变量都已经被赋值。 几个回溯变量存在。 回跳法 提高了校验一致性。 回跳法 允许保存的部分搜索通过回溯“一个以上的变量,“在某些情况下。 约束学习并节省了新约束,可后来用来避免部分的搜索。. 可预见性也常常在回溯法中应用,用来去预见选择一个变量或值的影响,因此常常用来预先判定一个子问题什么时候满足什么时候不满足。 约束传播 技术方法用来修饰一个约束补偿问题 说的更精确些,这些方法的一种形式,增强局部一致性, 这是有条件的一致性有关的一组变量和/或约束。约束传播应用在各个领域. 首先,它把问题转化为一个等价但通常是最简单的解决方法。 其次他可以用来证明满足和不满足问题。 这发生在一般没有保证的;但是,它总是会发生一些形式的约束传播和/或某些种类的问题。 最有名的惯用的局部一致性是 弧协调性超弧协调性,和路径协调性。 最流行的方法是AC-3约束传播算法,该算法可以执行弧的一致性。

局部搜索方法 是不完整的可满足性算法。 人们可能找到解决问题的方法, 但这方法可能令我们失望。他们工作,通过改变所有问题的变量来迭代算法。 。在每一步,少量的变量是改变价值,与整体目标数量的增加约束满足的任务。 最小冲突算法是局部搜索算法和基于特定CSPs原则。在实践中,局部搜索似乎工作当这些变化也受随机选择。整合搜索和局部搜索被开发了,导致混合算法

CSPs的理论方面[编辑]

判定问题[编辑]

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


功能问题[编辑]

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

CSPs的变型[编辑]

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

动态CSPs[编辑]

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

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

灵活的CSPs[编辑]

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

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

参见[编辑]

参考文献[编辑]

  1. ^ Bodirsky, Manuel; Pinsker, Michael. Schaefer's theorem for graphs. CoRR. 2010,. abs/1011.2894: 2894. arXiv:1011.2894. Bibcode:2010arXiv1011.2894B. 
  2. ^ Cai, Jin-Yi; Chen, Xi. Complexity of Counting CSP with Complex Weights. CoRR. 2011,. abs/1111.2384. 
  3. ^ . doi:10.1.1.9.6733.  缺少或|title=为空 (帮助)
  4. ^ Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks In Proc. of AAAI-88, 37-42. [1]
  5. ^ Solution reuse in dynamic constraint satisfaction problems, Thomas Schiex

扩展阅读[编辑]

超链接[编辑]