反饋

約束滿足問題

約束滿足問題（CSPs）是種數學的問題，其定義為一組對象(object)，而這些對象需要滿足一些限制或條件。

中文名: 約束滿足問題

外文名: CSPs

約束滿足問題簡介

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

約束滿足問題定義

正式來説，約束滿足問題定義為一個三元組

，其中

是變量的集合,

是各個變量的定義域集合,而

是限制條件的集合。

每個變量

可以在非空的定義域

中取出。每個限制條件(Constraint)

依序對應一對

，其中

是 {\displaystyle n} n-tuple的變量，

則是在定義域

中，其對應到的子集合上得到的

維的關係。變量的評估(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^[1] ，每一個都是轉變的前一個變量和約束可以添加或刪除限制(放鬆)。信息在初始的配方發現問題可以用來提煉下一個。解決的方法可分為根據信息的方法在轉讓:

Oracles: 解決之前發現的序列CSPs作為啓發式方法指導解決當前CSP從零開始。
Local repair: 每個CSP計算從解決部分問題之前的修復與Local search。局部搜索不約束。
Constraint recording: 新的約束是定義在每一階段的搜索代表學習羣決策不一致。在這些約束進行了新的CSP問題。

約束滿足問題靈活的CSPs

經典的CSPs處理約束很嚴格，意味着強制的 (每一解決方案必須滿足所有問題) 並且刻板的 (意味着,以至於他們必須被完全滿足,否則他們是完全違反了)。靈活的 CSPs 放寬假設, 部分的放寬限制對不遵循的的也一樣解決問題。這類似於preference-based planning. 一些類型的靈活 CSPs 包括: