|
|
| (405 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| In [[artificial intelligence]] and [[operations research]], '''constraint satisfaction''' is the process of finding a solution to a set of [[Constraint (mathematics)|constraint]]s that impose conditions that the [[Variable (mathematics)|variables]] must [[satisfiability|satisfy]]. A solution is therefore a vector of variables that satisfies all constraints.
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
|
| |
|
| The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are constraints on a finite domain, to the point that [[constraint satisfaction problem]]s are typically identified with problems based on constraints on a finite domain. Such problems are usually solved via [[Search algorithm|search]], in particular a form of [[backtracking]] or [[local search (constraint satisfaction)|local search]]. [[Constraint propagation]] are other methods used on such problems; most of them are incomplete in general, that is, they may solve the problem or prove it unsatisfiable, but not always. Constraint propagation methods are also used in conjunction with search to make a given problem simpler to solve. Other considered kinds of constraints are on real or rational numbers; solving problems on these constraints is done via [[variable elimination]] or the [[simplex algorithm]].
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| Constraint satisfaction originated in the field of [[artificial intelligence]] in the 1970s (see for example {{Harv|Laurière|1978}}). During the 1980s and 1990s, embedding of constraints into a [[programming language]] were developed. Languages often used for [[constraint programming]] are [[Prolog]] and [[C++]].
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| ==Constraint satisfaction problem== | | '''MathML''' |
| {{main|Constraint satisfaction problem}}
| | :<math forcemathmode="mathml">E=mc^2</math> |
|
| |
|
| As originally defined in artificial intelligence, constraints enumerate the possible values a set of variables may take. Informally, a finite domain is a finite set of arbitrary elements. A constraint satisfaction problem on such domain contains a set of variables whose values can only be taken from the domain, and a set of constraints, each constraint specifying the allowed values for a group of variables. A solution to this problem is an evaluation of the variables that satisfies all constraints. In other words, a solution is a way for assigning a value to each variable in such a way that all constraints are satisfied by these values.
| | <!--'''PNG''' (currently default in production) |
| | :<math forcemathmode="png">E=mc^2</math> |
|
| |
|
| In some circumstances, there may exist additional requirements: one may be interested not only in the solution (and in the fastest or most computationally efficient way to reach it) but in how it was reached; e.g. one may want the "simplest" solution ("simplest" in a logical, non computational sense that has to be precisely defined). This is often the case in logic games such as Sudoku.
| | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| In practice, constraints are often expressed in compact form, rather than enumerating all values of the variables that would satisfy the constraint. One of the most used constraints is the one establishing that the values of the affected variables must be all different.
| | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
|
| |
|
| Problems that can be expressed as constraint satisfaction problems are the [[Eight queens puzzle]], the [[Sudoku]] solving problem, the [[Boolean satisfiability problem]], [[Scheduling (production processes)|scheduling]] problems and various problems on graphs such as the [[graph coloring]] problem.
| | ==Demos== |
|
| |
|
| While usually not included in the above definition of a constraint satisfaction problem, arithmetic equations and inequalities bound the values of the variables they contain and can therefore be considered a form of constraints. Their domain is the set of numbers (either integer, rational, or real), which is infinite: therefore, the relations of these constraints may be infinite as well; for example, <math>X=Y+1</math> has an infinite number of pairs of satisfying values. Arithmetic equations and inequalities are often not considered within the definition of a "constraint satisfaction problem", which is limited to finite domains. They are however used often in [[constraint programming]].
| | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
|
| |
|
| ===Solving===
| |
|
| |
|
| Constraint satisfaction problems on finite domains are typically solved using a form of [[Search algorithm|search]]. The most used techniques are variants of [[backtracking]], [[constraint propagation]], and [[Local search (optimization)|local search]]. These techniques are used on problems with [[nonlinear]] constraints.
| | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| In case there is a requirement on "simplicity", a pure logic, pattern based approach was first introduced for the Sudoku CSP in the book {{lang|en|''The Hidden Logic of Sudoku''}}<ref name="The Hidden Logic of Sudoku">{{en}}{{cite news | first = Denis | last = Berthier | titre = {{lang|en|The Hidden Logic of Sudoku}} | url = http://www.carva.org/denis.berthier/HLS | work = Lulu Publishers, ISBN 978-1-84753-472-9 | date = 16 mai 2007 | accessdate = 16 mai 2007 }}</ref>. It has recently been generalized to any finite CSP in another book by the same author: {{lang|en|''Constraint Resolution Theories''}}<ref name="Constraint Resolution Theories">{{en}}{{cite news | first = Denis | last = Berthier | titre = {{lang|en|Constraint Resolution Theories}} | url = http://www.carva.org/denis.berthier/CRT | work = Lulu Publishers, ISBN 978-1-4478-6888-0 | date = 5 octobre 2011 | accessdate = 5 octobre 2011 }}</ref>.
| | ==Test pages == |
|
| |
|
| [[Variable elimination]] and the [[simplex algorithm]] are used for solving [[linear]] and [[polynomial]] equations and inequalities, and problems containing variables with infinite domain. These are typically solved as [[Optimization (mathematics)|optimization]] problems in which the optimized function is the number of violated constraints. | | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| ===Complexity===
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| {{main|Complexity of constraint satisfaction}}
| | *[[Url2Image|Url2Image (private Wikis only)]] |
| | | ==Bug reporting== |
| Solving a constraint satisfaction problem on a finite domain is an [[NP complete]] problem with respect to the domain size. Research has shown a number of [[Tractable problem|tractable]] subcases, some limiting the allowed constraint relations, some requiring the scopes of constraints to form a tree, possibly in a reformulated version of the problem. Research has also established relationship of the constraint satisfaction problem with problems in other areas such as [[finite model theory]].
| | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| | |
| A very different aspect of complexity appears when one fixes the size of the domain. It is about the complexity distribution of minimal instances of a CSP of fixed size (e.g. Sudoku(9x9)). Here, complexity is measured according to the above-mentioned "simplicity" requirement (see {{lang|en|''Unbiased Statistics of a CSP - A Controlled-Bias Generator'}}<ref name="Berthier-CBG">Denis Berthier, {{lang|en|''Unbiased Statistics of a CSP - A Controlled-Bias Generator''}}, {{lang|en|International Joint Conferences on Computer}}, {{lang|en|Information}}, {{lang|en|Systems Sciences and Engineering}} (CISSE 09), {{lang|en|December 4-12, 2009}}</ref> or {{lang|en|''Constraint Resolution Theories''}}<ref name="Constraint Resolution Theories"/>). In this context, a minimal instance is an instance with a unique solution such that if any given (or clue) is deleted from it, the resulting instance has several solutions (statistics can only be meaningful on the set of minimal instances).
| |
| | |
| ==Constraint programming==
| |
| {{main|Constraint programming}}
| |
| | |
| Constraint programming is the use of constraints as a programming language to encode and solve problems. This is often done by embedding constraints into a [[programming language]], which is called the host language. Constraint programming originated from a formalization of equalities of terms in [[Prolog II]], leading to a general framework for embedding constraints into a [[logic programming]] language. The most common host languages are [[Prolog]], [[C++]], and [[Java (programming language)|Java]], but other languages have been used as well.
| |
| | |
| ===Constraint logic programming===
| |
| {{main|Constraint logic programming}}
| |
| | |
| A constraint logic program is a [[Logic programming|logic program]] that contains constraints in the bodies of clauses. As an example, the clause <code>A(X):-X>0,B(X)</code> is a clause containing the constraint <code>X>0</code> in the body. Constraints can also be present in the goal. The constraints in the goal and in the clauses used to prove the goal are accumulated into a set called [[constraint store]]. This set contains the constraints the interpreter has assumed satisfiable in order to proceed in the evaluation. As a result, if this set is detected unsatisfiable, the interpreter backtracks. Equations of terms, as used in logic programming, are considered a particular form of constraints which can be simplified using [[unification (computing)|unification]]. As a result, the constraint store can be considered an extension of the concept of [[substitution]] that is used in regular logic programming. The most common kinds of constraints used in constraint logic programming are constraints over integers/rational/real numbers and constraints over finite domains.
| |
| | |
| [[Concurrent constraint logic programming]] languages have also been developed. They significantly differ from non-concurrent constraint logic programming in that they are aimed at programming [[concurrent process]]es that may not terminate. [[Constraint handling rules]] can be seen as a form of concurrent constraint logic programming, but are also sometimes used within a non-concurrent constraint logic programming language. They allow for rewriting constraints or to infer new ones based on the truth of conditions.
| |
| | |
| ===Constraint satisfaction toolkits===
| |
| | |
| Constraint satisfaction toolkits are [[Software library|software libraries]] for [[imperative programming language]]s that are used to encode and solve a constraint satisfaction problem.
| |
| | |
| * [[Cassowary constraint solver]] is an [[open source]] project for constraint satisfaction (accessible from C, Java, Python and other languages).
| |
| * [[Comet (programming language)|Comet]], a commercial programming language and toolkit | |
| * [[Gecode]], an open source portable toolkit written in C++ developed as a production-quality and highly efficient implementation of a complete theoretical background.
| |
| * [[JaCoP (solver)]] an open source [http://jacop.osolpro.com/ Java constraint solver]
| |
| * [http://www.koalog.com/ Koalog] a commercial Java-based constraint solver.
| |
| * [http://www.logilab.org/projects/constraint logilab-constraint] an open source constraint solver written in pure Python with constraint propagation algorithms.
| |
| * [http://minion.sourceforge.net/ MINION] an open-source constraint solver written in C++, with a small language for the purpose of specifying models/problems.
| |
| * [http://www.bracil.net/CSP/cacp/cacpdemo.html ZDC] is an open source program developed in the [http://www.bracil.net/CSP/cacp/ Computer-Aided Constraint Satisfaction Project] for modelling and solving constraint satisfaction problems.
| |
| | |
| ===Other constraint programming languages===
| |
| | |
| Constraint toolkits are a way for embedding constraints into an [[imperative programming language]]. However, they are only used as external libraries for encoding and solving problems. An approach in which constraints are integrated into an imperative programming language is taken in the [[Kaleidoscope programming language]].
| |
| | |
| Constraints have also been embedded into [[Functional programming|functional programming languages]].
| |
| | |
| == See also ==
| |
| | |
| * [[Constraint satisfaction problem]]
| |
| * [[Constraint (mathematics)]]
| |
| * [[Candidate solution]]
| |
| * [[Boolean satisfiability problem]]
| |
| * [[Decision theory]]
| |
| * [[Satisfiability modulo theories]]
| |
| | |
| ==References==
| |
| {{reflist}}
| |
| *{{cite book
| |
| | last=Apt| first=Krzysztof
| |
| | title=Principles of constraint programming
| |
| | publisher=Cambridge University Press
| |
| | year=2003
| |
| | isbn=0-521-82583-0
| |
| }}
| |
| *{{cite book
| |
| | last=Berthier| first=Denis
| |
| | title=Constraint Resolution Theories
| |
| | publisher=Lulu
| |
| | year=2011
| |
| | url=http://www.carva.org/denis.berthier/CRT
| |
| | isbn=978-1-4478-6888-0
| |
| }}
| |
| *{{cite book
| |
| | last=Dechter | first=Rina
| |
| | title=Constraint processing
| |
| | publisher=Morgan Kaufmann
| |
| | year=2003
| |
| | url=http://www.ics.uci.edu/~dechter/books/index.html
| |
| | isbn=1-55860-890-7
| |
| }}
| |
| *{{cite journal
| |
| | last=Dincbas | first=M.
| |
| | last2=Simonis | first2=H.
| |
| | last3=Van Hentenryck | first3=P.
| |
| | year= 1990
| |
| | title=Solving Large Combinatorial Problems in Logic Programming
| |
| | journal=Journal of logic programming
| |
| | volume=8 | issue=1–2
| |
| | pages=75–93
| |
| | doi=10.1016/0743-1066(90)90052-7
| |
| }}
| |
| *{{cite book
| |
| | first=Eugene
| |
| | last=Freuder
| |
| | coauthors=Alan Mackworth (ed.)
| |
| | title=Constraint-based reasoning
| |
| | publisher=MIT Press
| |
| | year=1994
| |
| }}
| |
| *{{cite book
| |
| | last=Frühwirth | first=Thom
| |
| | coauthors=Slim Abdennadher
| |
| | title=Essentials of constraint programming
| |
| | year=2003
| |
| | publisher=Springer
| |
| | isbn=3-540-67623-6
| |
| }}
| |
| *{{cite book
| |
| | last=Guesguen | first=Hans
| |
| | coauthors=Hertzberg Joachim
| |
| | title=A Perspective of Constraint Based Reasoning
| |
| | year=1992
| |
| | publisher=Springer
| |
| | isbn=978-3-540-55510-0
| |
| }}
| |
| *{{cite journal
| |
| | last=Jaffar | first=Joxan
| |
| | coauthors=Michael J. Maher
| |
| | title=Constraint logic programming: a survey
| |
| | journal=Journal of logic programming
| |
| | volume=19/20
| |
| | pages=503–581
| |
| | year=1994
| |
| | doi=10.1016/0743-1066(94)90033-7
| |
| }}
| |
| *{{cite journal
| |
| | last=Laurière | first=Jean-Louis
| |
| | year=1978
| |
| | title=A Language and a Program for Stating and Solving Combinatorial Problems
| |
| | journal=[[Artificial Intelligence (journal)|Artificial intelligence]]
| |
| | volume=10 | issue=1
| |
| | pages=29–127
| |
| | doi=10.1016/0004-3702(78)90029-2
| |
| }}
| |
| *{{cite book
| |
| | last=Lecoutre | first=Christophe
| |
| | 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
| |
| | isbn=978-1-84821-106-3
| |
| }}
| |
| *{{cite book
| |
| | last=Marriot | first=Kim
| |
| | coauthors=Peter J. Stuckey
| |
| | title=Programming with constraints: An introduction
| |
| | year=1998
| |
| | publisher=MIT Press
| |
| | isbn=0-262-13341-5
| |
| }}
| |
| *{{cite book
| |
| | last=Rossi | first=Francesca
| |
| | coauthors=Peter van Beek, Toby Walsh (ed.)
| |
| | title=Handbook of Constraint Programming,
| |
| | publisher=Elsevier
| |
| | year=2006
| |
| | url=http://www.elsevier.com/wps/find/bookdescription.cws_home/708863/description#description
| |
| | isbn=978-0-444-52726-4 0-444-52726-5
| |
| }}
| |
| *{{cite book
| |
| | first=Edward
| |
| | last=Tsang
| |
| | title=Foundations of Constraint Satisfaction
| |
| | publisher=Academic Press
| |
| | year=1993
| |
| | url=http://www.bracil.net/edward/FCS.html
| |
| | isbn=0-12-701610-4
| |
| }}
| |
| *{{cite book
| |
| | first=Pascal
| |
| | last=Van Hentenryck
| |
| | title=Constraint Satisfaction in Logic Programming
| |
| | publisher=MIT Press
| |
| | year=1989
| |
| | isbn=0-262-08181-4
| |
| }}
| |
| | |
| ==External links==
| |
| *[http://4c.ucc.ie/web/outreach/tutorial.html CSP Tutorial]
| |
| | |
| {{DEFAULTSORT:Constraint Satisfaction}}
| |
| [[Category:Constraint programming| ]]
| |
| [[hy:Հարկադիր պարտավորությունների կատարում]]
| |
