Philosophy Dictionary of ArgumentsHome
| |||
|
| |||
| Constraint Satisfaction Problems: In computer science, a constraint satisfaction problem (CSP) is a problem where we have a set of variables and a set of constraints that specify which values the variables can take. The goal is to find an assignment of values to the variables that satisfies all the constraints._____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. | |||
| Author | Concept | Summary/Quotes | Sources |
|---|---|---|---|
|
Peter Norvig on Constraint Satisfaction Problems - Dictionary of Arguments
Norvig I 202 Constraint Satisfaction Problems/CSP/artificial intelligence/Norvig/Russell: Problem: if each state is atomic, or invisible - a black box with no internal structure, problems can [only] be solved by searching in a space of states. These states can be evaluated by domain-specific heuristics and tested to see whether they are goal states. Solution: We use a factored representation for each state: a set of variables, each of which has a value. A problem is solved when each variable has a value that satisfies all the constraints on the variable. CSP search algorithms take advantage of the structure of states and use general-purpose rather than problem-specific heuristics to enable the solution of complex problems. The main idea is to eliminate large portions of the search space all at once by identifying variable/value combinations that violate the constraints. A constraint satisfaction problem consists of three components, X,D, and C: X is a set of variables, {X1, . . . ,Xn}. D is a set of domains, {D1, . . . ,Dn}, one for each variable. C is a set of constraints that specify allowable combinations of values. Norvig I 203 It can be helpful to visualize a CSP as a constraint graph, (…) The nodes of the graph correspond to variables of the problem, and a link connects any two variables that participate in a constraint. E.g., once we have chosen [a color] in the [map coloring] problem, we can conclude that none of the five neighboring variables can take on the value [of the same color]. Norvig I 205 Problem: A discrete domain can be infinite, such as the set of integers or strings. Solution: a constraint language must be used that understands constraints (…) directly, without enumerating the set of pairs of allowable values (…).Special solution algorithms (…) exist for linear constraints on integer variables—that is, constraints, (…), in which each variable appears only in linear form. Problem: It can be shown that no algorithm exists for solving general nonlinear constraints on integer variables. Norvig I 206 Continuous domains: Constraint satisfaction problems with continuous domains are common in the real world and are widely studied in the field of operations research. For example, the scheduling of experiments on the Hubble Space Telescope requires very precise timing of observations (…). The best-known category of continuous-domain CSPs is that of linear programming problems, where constraints must be linear equalities or inequalities. >Linear programming/Norvig. Norvig I 208 In regular state-space search, an algorithm can do only one thing: search. In CSPs there is a choice: an algorithm can search (choose a new variable assignment from several possibilities) or do a specific type of inference called constraint propagation: using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on. Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts. Sometimes this preprocessing can solve the whole problem, so no search is required at all. Norvig I 227 Constraint satisfaction problems (CSPs) represent a state with a set of variable/value pairs and represent the conditions for a solution by a set of constraints on the variables. Many important real-world problems can be described as CSPs. A number of inference techniques use the constraints to infer which variable/value pairs are consistent and which are not. These include node, arc, path, and k-consistency. Backtracking search, a form of depth-first search, is commonly used for solving CSPs. Inference can be interwoven with search. The minimum-remaining-values and degree heuristics are domain-independent methods for deciding which variable to choose next in a backtracking search. The least constraining- value heuristic helps in deciding which value to try first for a given variable. Backtracking occurs when no legal assignment can be found for a variable. Conflict-directed backjumping backtracks directly to the source of the problem. Local search using the min-conflicts heuristic has also been applied to constraint satisfaction problems with great success. History: The earliest work related to constraint satisfaction dealt largely with numerical constraints. Equational constraints with integer domains were studied by the Indian mathematician Brahmagupta in the seventh century; they are often called Diophantine equations (…). Systematic methods for solving linear equations by variable elimination were studied by Gauss (1829(1)); the solution of linear inequality constraints goes back to Fourier (1827)(2). Finite-domain constraint satisfaction problems also have a long history. For example, graph coloring (of which map coloring is a special case) is an old problem in mathematics. The four-color conjecture (that every planar graph can be colored with four or fewer colors) was first made by Francis Guthrie, a student of De Morgan, in 1852. It resisted solution - despite several published claims to the contrary - until a proof was devised by Appel and Haken (1977)(3) (see the book Four Colors Suffice (Wilson, 2004)(4)). Purists were disappointed that part of the proof relied on a computer, so Georges Gonthier (2008)(5), using the COQ theorem prover, derived a formal proof that Appel and Haken’s proof was correct. Norvig I 228 Constraint propagation methods were popularized by Waltz’s (1975)(6) success on polyhedral line-labeling problems for computer vision. Waltz showed that, in many problems, propagation completely eliminates the need for backtracking. Montanari (1974)(7) introduced the notion of constraint networks and propagation by path consistency. Alan Mackworth (1977)(8) proposed the AC-3 algorithm for enforcing arc consistency as well as the general idea of combining backtracking with some degree of consistency enforcement. AC-4, a more efficient arc-consistency algorithm, was developed by Mohr and Henderson (1986)(9). Soon after Mackworth’s paper appeared, researchers began experimenting with the tradeoff between the cost of consistency enforcement and the benefits in terms of search reduction. Haralick and Elliot (1980)(10) favored the minimal forward-checking algorithm described by McGregor (1979)(11), whereas Gaschnig (1979)(12) suggested full arc-consistency checking after each variable assignment—an algorithm later called MAC by Sabin and Freuder (1994)(13). Special methods for handling higher-order or global constraints were developed first within the context of constraint logic programming. Marriott and Stuckey (1998)(14) provide excellent coverage of research in this area. 1. Gauss, C. F. (1829). Beiträge zur Theorie der algebraischen Gleichungen. Collected in Werke, Vol. 3, pages 71–102. K. Gesellschaft Wissenschaft, Göttingen, Germany, 1876. 2. Fourier, J. (1827). Analyse des travaux de l’Academie Royale des Sciences, pendant l’annee 1824; partie mathematique. Histoire de l’Academie Royale des Sciences de France, 7, xlvii–lv. 3. Appel, K. and Haken, W. (1977). Every planar map is four colorable: Part I: Discharging. Illinois J. Math., 21, 429–490 4. Wilson, R. (2004). Four Colors Suffice. Princeton University Press. 5. Gonthier, G. (2008). Formal proof–The four-color theorem. Notices of the AMS, 55(11), 1382–1393. 6. Waltz, D. (1975). Understanding line drawings of scenes with shadows. In Winston, P. H. (Ed.), The Psychology of Computer Vision. McGraw-Hill. 7. Montanari, U. (1974). Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7(2), 95–132. 8. Mackworth, A. K. (1977). Consistency in networks of relations. AIJ, 8(1), 99–118. 9. Mohr, R. and Henderson, T. C. (1986). Arc and path consistency revisited. AIJ, 28(2), 225–233. 10. Haralick, R. M. and Elliot, G. L. (1980). Increasing tree search efficiency for constraint satisfaction problems. AIJ, 14(3), 263–313. 11. McGregor, J. J. (1979). Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. Information Sciences, 19(3), 229–250. 12. Gaschnig, J. (1977). A general backtrack algorithm that eliminates most redundant tests. In IJCAI-77, p. 457. 13. Sabin, D. and Freuder, E. C. (1994). Contradicting conventional wisdom in constraint satisfaction. In ECAI-94, pp. 125–129. 14. Marriott, K. and Stuckey, P. J. (1998). Programming with Constraints: An Introduction. MIT Press._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition. |
Norvig I Peter Norvig Stuart J. Russell Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010 |
||
> Counter arguments against Norvig
> Counter arguments in relation to Constraint Satisfaction Problems
Ed. Martin Schulz, access date 2024-04-26