約束滿足問題

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

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

• 八皇后問題
• 圖著色問題
• 填字遊戲、數獨及其他一些邏輯益智遊戲

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

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

正式的定義

正式來說，約束滿足問題定義為一個三元組$\langle X,D,C\rangle$,其中

$X=\{X_{1},...,X_{n}\}$ 是變數的集合,

$D=\{D_{1},...,D_{n}\}$ 是各個變數的定義域集合,而

$C=\{C_{1},...,C_{n}\}$ 是限制條件的集合。

每個變數$X_{i}$可以在非空的定義域$D_{i}$中取出。每個限制條件(Constraint)$C_{j}\in C$依序對應一對$\langle t_{j},R_{j}\rangle$,其中 $t_{j}\subset X$ 是變數的$k$元组，$R_{j}$ 則是在定義域$D_{i}$中，其對應到的子集合上得到的$k$元组的關係。 變數的定值(evaluation或assignment)是一個函數，其從變數的子集合映射到該變數子集合所對應到的定義域子集合中特定的值組成的集合，也就是

$f:X'\rightarrow V$其中$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}}$。

如果 $f(X_{p_{1}}),\ldots ,f(X_{p_{k}})\in R_{j}$，則此定值$f$滿足條件限制$\langle t_{j},R_{j}\rangle$ 。

如果一個定值不違反任何的條件限制，我們說這個定值是無矛盾的(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的变型

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

动态CSPs

动态CSPs (DCSPs) 是有用的，当原有的问题形式以某种方式改变，通常是由于约束集进化，因为要考虑环境。 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模糊的约束关系，在这种情况下约束满足是变量的连续函数，从完全满足到完全不满足。

参见

• 约束满足
• 声明式编程
• 规划约束
• 分布式约束满足问题 (DisCSP)

扩展阅读

• 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. 

超链接

• CSP Tutorial

• Tsang, Edward. Foundations of Constraint Satisfaction. Academic Press. 1993.  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.  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.  ISBN 978-1-84821-106-3
• Tomás Feder, Constraint satisfaction: a personal perspective, manuscript.
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB
• Benchmarks -- XML representation of CSP instances
• Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning, Ian Miguel - slides.
• Constraint Propagation - Dissertation by Guido Tack giving a good survey of theory and implementation issues