A Constraint Satisfaction Task is a Classification Task that requires a Decision Act on whether there exists a Solution which satisfies the Constraints, and may require that the Solution be reported.
References
2009
- (Wikipedia, 2009) http://en.wikipedia.org/wiki/Constraint_satisfaction
- In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.
- 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 problems are typically identified with problems based on constraints on a finite domain. Such problems are usually solved via search, in particular a form of backtracking or 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.
- Constraint satisfaction originated in the field of artificial intelligence in the 1970s. During the 1980s and 1990s, embedding of constraints into a programming language were developed. Languages often used for constraint programming are Prolog and C++.
- (Wikipedia, 2009) http://en.wikipedia.org/wiki/Constraint_satisfaction_problem
- Constraint satisfaction problems or CSPs are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time.
- Examples of problems that can be modeled as a constraint satisfaction problem:
- Eight queens puzzle
- Map coloring problem
- Sudoku
- Boolean satisfiability
1994