约束补偿问题

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

約束補償問題(CSPs)是種數學的問題,其定義為一組物件(object),而這些物件需要滿足一些限制或條件。 CSPs將其問題中的單元(entities)表示成在變數上有限條件的一組同質(homogeneous)的集合, 這類問題透過"約束補償方法"來解決。CSPs是人工智慧運籌學 的熱門主題,因為它們公式中的規律,提供了共同基礎來分析、解決很多看似不相關的問題。 CSPs通常呈現高複雜性, 需要同時透過啟發式搜索聯合搜索 的方法,來在合理的時間內解決問題。 布林可滿足性問題 (SAT), 可滿足性的理論 (SMT)和回答集程式設計 (ASP) 可以算是某種程度上的約束補償問題。

以下舉例為幾個簡單的約束滿足問題:

這些是提供的ASP,Boolean SAT和SMT教學課程的人通常會教的。在一般情况下,約束問題會是更 困難,而且可能難以用這些簡單系統的例子來表達。

現實生活中的例子包含自動規劃資源配置

正式的定義[编辑]

正式來說,約束補償問題定義為一個三元組,其中

是變數的集合,
是各個變數的定義域集合,而
是限制條件的集合。

每個變數可以在非空的定義域中取出。每個限制條件(Constraint)依序對應一對,其中 -tuple的變數, 則是在定義域中,其對應到的子集合上得到的-ary 維的關係。 變數的評估(evaluation)是一個函數,其從變數的子集合映射到一組特定的集合,集合內為定義域的子集合所對應到的值,也就是

如果 ,則此評估(evaluation)滿足條件限制

如果一個評估不違反任何的條件限制,我們說這個評估是無矛盾的(consistent)。 如果一個評估包含了所有的變數,我們說這個評估是完備的(complete)。 如果一個評估無矛盾而且完備的,我們說這個評估是一個解(solution),這樣的評估就會用來解決CSP。

CSPs的解決方法[编辑]

定義域有限的約束滿足問題通常利用搜索方法來解決。最常用的技術是回溯法(backtracking)、約束傳遞constraint propagation,以及局部搜索local search的改良。

回溯法 是一種遞迴演算法,它保持部分變數的賦值。一開始,所有的變數都還沒被賦值。在每一個步驟中,先選取一個變數,並且將所有可能的值依次賦予該變數。對於每一個值,在限制條件下的局部賦值的無矛盾性(consistency)都進行檢查。在符合無矛盾(consistency)的情況下,就會遞迴地往下呼叫。當所有的值都試過,演算法則回溯上層。在這個基本回溯演算法中,無矛盾性(consistency)被定義為滿足所有的條件限制,且這些條件限制的變數已被賦值。若干回溯變數存在。 回溯法 提高了檢查無矛盾性的效率。 回跳法 可以使在某些在某些情況中,透過回溯”一個以上的變數“,來省去部分的搜尋。 約束學習則藉由減少新的條件限制,來避免部分的搜尋。 可預見性也常常在回溯法中應用,用來去預期選擇一個變數或值的影響,因此常常用來預先判定一個子問題什麼時候滿足或不滿足。 約束傳遞 (Constraint propagation)技術是用來修飾一個CSP的方法。更精確地說,是一種方法,用來增強一種形式的局部一致性,是一種條件牽連到一組變數或條件限制的一致性。約束傳播應用在各個領域。一來,它把問題轉化為一個等價但通常是最簡單的解決方法。 二來,他可以用來驗證滿足或不滿足於問題。 一般來說他不保證會發生,但是它總是會發生一些形式的約束傳遞(Constraint propagation)或某些種類的問題。 最有名的慣用的局部一致性是 弧協調性超弧一致性,和路徑一致性。 最流行的方法是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. ^ 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 (英语). 
  4. ^ Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks In Proc. of AAAI-88, 37-42.
  5. ^ Solution reuse in dynamic constraint satisfaction problems, Thomas Schiex

扩展阅读[编辑]

超链接[编辑]