約束滿足問題

約束滿足問題（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