Constraint Satisfaction Algorithm
A Constraint Satisfaction Algorithm is an Algorithm (a Satisficing Algorithm?) that can solve a Constraint Satisfaction Task.
- AKA: CSP Algorithm.
- …
- Example(s):
- See: Backtracking Algorithm, Satisfiability, Feasible Region, Finite Domain Constraint, Search Algorithm, Local Search (Constraint Satisfaction), Constraint Propagation, Variable Elimination.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Constraint_satisfaction Retrieved:2014-9-30.
- 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 set of values for the variables that satisfies all constraints—that is, a point in the feasible region.
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 (see for example). During the 1980s and 1990s, embedding of constraints into a programming language were developed. Languages often used for constraint programming are Prolog and C++.
- 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 set of values for the variables that satisfies all constraints—that is, a point in the feasible region.
2009
- (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Constraint_satisfaction
- Solving
- Constraint satisfaction problems on finite domains are typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and local search. These techniques are used on problems with nonlinear constraints.
- 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 problems in which the optimized function is the number of violated constraints.
- Solving
2008
- (Jones, 2008) ⇒ M. Tim Jones. (2008). “Artificial Intelligence: A Systems Approach." Jones & Bartlett. ISBN:0763773379
- A large number algorithms exist to solve CSPs from the simple Generate and Test algorithm to constraint-propagation and consistency. We'll explore a few of the available algorithms that can be used. Note that some of the algorithms we've discussed thus far (such as depth-first search invested in Chapter 2, and simulated annealing and Tabu search from Chapter 3) can be used effectively to solve CSPs