查看“︁約束滿足問題”︁的源代码

{{noteTA
|G1 = Math
}}
'''約束滿足問題'''（'''Constraint satisfaction problem'''，'''CSPs'''）是種數學的問題，其定義為一組物件（object），而這些物件需要滿足一些限制或條件。CSPs將其問題中的單元（entities）表示成在[[變數]]上有限條件的一組同質（homogeneous）的集合，這類問題透過「約束滿足方法」來解決。CSPs是[[人工智能|人工智慧]]和[[運籌學]]的熱門主題，因為它們公式中的規律，提供了共同基礎來分析、解決很多看似不相關的問題。通常{{tsl|en|Complexity of constraint satisfaction||約束滿足問題具有高度複雜性}}，需要同時透過[[啟發式演算法|啟發式搜索]]和{{tsl|en|Combinatorial search||聯合搜索}}的方法，來在合理的時間內解決問題。[[布尔可满足性问题|布林可滿足性問題]]（SAT），{{tsl|en|Satisfiability modulo theories||可滿足性的理論}}（SMT）和[[回答集编程|回答集程式設計]]（ASP）可以算是某種程度上的約束滿足問題。

以下舉例為幾個簡單的約束滿足問題:
* [[八皇后問題]]
* [[图着色问题|圖著色問題]]
* [[填字游戏|填字遊戲]]、[[數獨]]及其他一些[[邏輯益智遊戲]]

這些ASP是BooleanSAT和SMT教學課程的人常會使用的範例。在現實情况下，約束滿足問題通常更困難，且難以用簡單的範例來表達，例如{{tsl|en|Automated planning and scheduling||自動規劃}}和[[资源分配|資源配置]]。

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

:<math>X=\{X_1,...,X_n\}</math>是變數的集合，
:<math>D=\{D_1,...,D_n\}</math>是各個變數的定義域集合，而
:<math>C=\{C_1,...,C_n\}</math>是限制條件的集合。
每個變數<math>X_i</math>可以在非空的定義域<math>D_i</math>中取出。每個限制條件（Constraint）<math>C_j\in C</math>依序對應一對<math>\langle t_j,R_j \rangle</math>，其中<math>t_j\subset X</math>是變數的<math>k</math>[[多元组|元组]]，<math>R_j</math>則是在定義域<math>D_i</math>中，其對應到的子集合上得到的<math>k</math>元组的[[二元关系|關係]]。變數的定值（evaluation或assignment）是一個函數，其從變數的子集合映射到該變數子集合所對應到的定義域子集合中特定的值組成的集合，也就是
:<math>f:X' \rightarrow V</math>其中<math>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}</math>。
如果<math>f(X_{p_1}),\ldots,f(X_{p_k}) \in R_j</math>，則此定值<math>f</math>滿足條件限制<math>\langle t_j,R_j \rangle</math>。

如果一個定值不違反任何的條件限制，我們說這個定值是無矛盾的（consistent）。
如果一個定值包含了所有的變數，我們說這個定值是完備的（complete）。
如果一個定值無矛盾而且完備的，我們說這個定值是一個解（solution），這樣的定值就是CSP的解。<ref name=Russell2010>{{cite book|author1=Stuart Jonathan Russell |author2=Peter Norvig |title=Artificial Intelligence: A Modern Approach|url=https://archive.org/details/nlsiu.340.11.rus.27359 |date=2010|publisher=Prentice Hall|isbn=9780136042594|page=Chapter 6}}</ref>

==解決方法==
定義域有限的約束滿足問題通常利用[[Search algorithm|搜索]]方法來解決。最常用的技術是[[回溯法]]（backtracking）、約束傳遞[[constraint propagation]]，以及局部搜索[[local search]]的改良。

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

[[Local search (最優化)|局部搜索方法]]是不完全滿足的演算法。人們可能找到解決問題的方法，但這方法可能令我們失望。其反覆更改變數來改進整個任務，而得以運作。在每一步，要更改少量變數的值，與整體目標數量的增加條件限制以滿足的任務。[[最小衝突演算法]]是局部搜索演算法和基於特定CSPs原則。在實踐中，局部搜索似乎工作當這些變化也受隨機選擇。整合搜索和局部搜索被開發了，導致[[Hybrid algorithm (constraint satisfaction)|混合演算法]]。

==理论==
===判定问题===
CSPs也研究[[计算复杂性问题]]和[[有限模型理论]]。一个重要的问题是，是否为每一组的关系、套都可视为CSPs选自只使用关系设置不是在[[P (complexity)|p]]或[[NP-完全]]问题。如果这样一个[[二分法]]真实可靠，那么CSPs提供已知的最大的一个[[NP (複雜度)|NP]]子集，避免[[NP-intermediate]]问题，其存在是证明了[[Ladner's 理论|Ladner's理论]]在这种假定下[[P versus NP problem|P≠NP]]。[[Schaefer's 二分法理论|Schaefer's二分法理论]]处理所用变量相关时的情况[[布尔数学运算符]]，也就是，对一个定义域大小为2的。最近的一个促进dichotomoy二分定理推广到一个更大的类的事务。<ref>{{cite journal
| last1        = Bodirsky
| first1       = Manuel
| last2        = Pinsker
| first2       = Michael
| year         = 2010
| title        = Schaefer's theorem for graphs
| pages        = 2894
| journal      = CoRR
| volume       = abs/1011.2894
| arxiv        = 1011.2894
| bibcode        = 2010arXiv1011.2894B}}</ref>

<!--大多数类CSPs容易处理,众所周知,[[超图]] 边界约束[[treewidth]] (和不受限制约束关系的集合)，或在有约束的状态,但是本质上任意存在非一元多态性{{Clarify|date=February 2009}} 成立的约束关系。
每个CSP也可以被视为一种过程控制问题查询 <ref>{{Cite journal
| last = Kolaitis
| first = Phokion G.
| last2 = Vardi
| first2 = Moshe Y.
| title = Conjunctive-Query Containment and Constraint Satisfaction
| journal = Journal of Computer and System Sciences
| volume = 61
| issue = 2
| pages = 302–332
| year = 2000
| doi = 10.1006/jcss.2000.1713}}</ref>
-->

===功能问题===
相同的情形存在于功能类别之间，[[FP (complexity)|FP]]和[[Sharp-P|#P]]。通过一般的[[Ladner's 理论|Ladner's理论]]，FP和[[Sharp-P-complete|#P-complete]]也存在问题如果FP≠#P。在这种决策下，一个#CSP问题被定义为一组关系。每个问题需要输入[[Boolean logic|布尔]]公式作为输入，任务是计算数字令人满意的工作。这可以进一步推广利用大域大小和附上一个权重，对每一个满意的赋值和计算这些权值的总和。众所周知任何复杂的#CSP权重问题既不是FP也不是#P-hard问题。<ref>{{cite journal
 |last1        = Cai
 |first1       = Jin-Yi
 |last2        = Chen
 |first2       = Xi
 |year         = 2011
 |title        = Complexity of Counting CSP with Complex Weights
 |journal      = CoRR
 |volume       = abs/1111.2384
 |url          = http://arxiv.org/abs/1111.2384
 |access-date  = 2012-04-08
 |archive-date = 2017-01-17
 |archive-url  = https://web.archive.org/web/20170117025909/https://arxiv.org/abs/1111.2384
}}</ref>

== 变型 ==
经典的造型约束满足问题定义了一个静态模型，呆板的约束。这个严格的模型的缺点是他很难容易的表现问题<ref>{{cite web|title=Dynamic Flexible Constraint Satisfaction and its Application to AI Planning (2001)|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.6733|author=Ian Miguel|id=hdl:1842/326 doi:10.1.1.9.6733|accessdate=2014-05-04|language=en|publisher=University of Edinburgh School of Informatics|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304085311/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.6733}}</ref>。基于CSP定义的几种修改，提出使该模型广泛适应各种各样的问题。
=== 动态CSPs ===
'''动态CSPs'''<ref>{{Cite web |url=http://www.ics.uci.edu/%7Ecsp/r5.pdf |title=Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks In Proc. of AAAI-88, 37-42. |access-date=2012-04-08 |archive-url=https://web.archive.org/web/20121117042241/http://www.ics.uci.edu/%7Ecsp/r5.pdf |archive-date=2012-11-17 |dead-url=yes }}</ref>（[[DCSP]]s）是有用的，当原有的问题形式以某种方式改变，通常是由于约束集进化，因为要考虑环境<ref>[http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf Solution reuse in dynamic constraint satisfaction problems] {{Wayback|url=http://www.aaai.org/Papers/AAAI/1994/AAAI94-302.pdf |date=20161225060222 }}, Thomas Schiex</ref>。DCSPs被当做一系列的静态CSPs，每一个都是转变的前一个变量和约束可以添加或删除限制（放松）。信息在初始的配方发现问题可以用来提炼下一个。解决的方法可分为根据信息的方法在转让:
* Oracles:解决之前发现的序列CSPs作为启发式方法指导解决当前CSP从零开始。
* Localrepair:每个CSP计算从解决部分问题之前的修复与[[Local search (optimization)|Local search]]。[[局部搜索]]不约束。
* Constraintrecording:新的约束是定义在每一阶段的搜索代表学习群决策不一致。在这些约束进行了新的CSP问题。

=== 灵活的CSPs ===
经典的CSPs处理约束很严格，意味着''强制的''（每一解决方案必须满足所有问题）并且''刻板的''（意味着，以至于他们必须被完全满足，否则他们是完全违反了）。'''灵活的CSP'''s放宽假设，部分的''放宽''限制对不遵循的的也一样解决问题。这类似于[[preference-based planning]]。一些类型的灵活CSPs包括:
* MAX-CSP，在那里有好些约束允许受侵犯的质量，并通过测量方法多少满意的约束。
* 加权CSP，使每一个MAX-CSP违反约束加权根据预定义的偏好。因此，更重要的是满足约束的优先考虑。
* CSP[[fuzzy logic|模糊的]]约束关系，在这种情况下约束满足是变量的连续函数，从完全满足到完全不满足。

==参见==
* [[约束补偿|约束]]满足
* [[声明式编程]]
* [[规划约束]]
* [[DisCSP|分布式约束满足问题]]（DisCSP）

== 参考文献 ==
<references/>

== 扩展阅读 ==
* {{cite journal|author=Steven Minton, Andy Philips, Mark D. Johnston, Philip Laird|title=Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems|journal=Journal of Artificial Intelligence Research|year=1993|volume=58|pages=161–205|url=https://eprints.kfupm.edu.sa/50799/1/50799.pdf|format=PDF}}{{dead link|date=2018年1月 |bot=InternetArchiveBot |fix-attempted=yes }}

==超链接==
*[https://web.archive.org/web/20090211163302/http://4c.ucc.ie/web/outreach/tutorial.html CSPTutorial]

*{{cite book
| first=Edward
| last=Tsang
| title=Foundations of Constraint Satisfaction
| year=1993
| publisher=Academic Press
| url=http://www.bracil.net/edward/FCS.html
| access-date=2012-04-08
| archive-date=2021-04-23
| archive-url=https://web.archive.org/web/20210423052600/https://www.bracil.net/edward/fcs.html
}}ISBN 0-12-701610-4
*{{cite journal|first1=Hubie|last1=Chen|date=December 2009|title=A Rendezvous of Logic, Complexity, and Algebra|journal=ACM Computing Surveys|publisher=ACM|doi=10.1145/1592451.1592453|pages=1–32 |volume=42|issue=1}}
*{{cite book
| first=Rina
| last=Dechter
| title=Constraint processing
| publisher=Morgan Kaufmann
| year=2003
| url=http://www.ics.uci.edu/~dechter/books/index.html
| access-date=2012-04-08
| archive-date=2021-04-25
| archive-url=https://web.archive.org/web/20210425042429/https://www.ics.uci.edu/~dechter/books/index.html
}}ISBN 1-55860-890-7
*{{cite book
| first=Krzysztof
| last=Apt
| title=Principles of constraint programming
| url=https://archive.org/details/principlesofcons0000aptk
| publisher=Cambridge University Press
| year=2003
}}ISBN 0-521-82583-0
*{{cite book
| first=Christophe
| last=Lecoutre
| title=Constraint Networks: Techniques and Algorithms
| publisher=ISTE/Wiley
| year=2009
| url=http://www.iste.co.uk/index.php?f=a&ACTION=View&id=250
| access-date=2012-04-08
| archive-date=2017-11-07
| archive-url=https://web.archive.org/web/20171107071437/http://www.iste.co.uk/index.php?f=a&ACTION=View&id=250
}}ISBN 978-1-84821-106-3
* TomásFeder，[http://theory.stanford.edu/~tomas/consmod.pdf ''Constraintsatisfaction:apersonalperspective'']{{Wayback|url=http://theory.stanford.edu/~tomas/consmod.pdf |date=20210119125707 }}，manuscript.
* [https://web.archive.org/web/20060213071549/http://4c.ucc.ie/web/archive/index.jsp Constraintsarchive]
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm ForcedSatisfiableCSPBenchmarksofModelRB]{{Wayback|url=http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm |date=20210125071920 }}
* [https://web.archive.org/web/20060813201559/http://www.cril.univ-artois.fr/~lecoutre/research/benchmarks/benchmarks.html Benchmarks--XMLrepresentationofCSPinstances]
* [https://web.archive.org/web/20090206055207/http://www.cs.st-andrews.ac.uk/~ianm/docs/Thesis.ppt DynamicFlexibleConstraintSatisfactionandItsApplicationtoAIPlanning]，IanMiguel-slides.
*[https://web.archive.org/web/20090419182234/http://www.ps.uni-sb.de/Papers/abstracts/tackDiss.html ConstraintPropagation]-DissertationbyGuidoTackgivingagoodsurveyoftheoryandimplementationissues
{{应用数学}}

{{DEFAULTSORT:Constraint Satisfaction Problem}}
[[Category:宣告式編程]]