constraint satisfaction
constraint satisfaction The process of resolving conflicts by removing or reconciling inconsistent values in a constraint network. A constraint network is a system of constraint equations and inequalities that represent the structure of a given problem. A crossword is an example of a constraint problem; the row/column sizes limit the choice of possible words and the interactions of rows and columns further constrain the solution.
The first stage in constraint satisfaction is constraint propagation, where any dependencies between constraints are exploited to introduce more constraint and thus reduce the solution space. Then follows a search where variables are assigned values and matched against current constraints; this involves further constraint propagation and backtracking from failures. A solution is produced when a single set of values fits the final reduced set of constraints. An overconstrained problem will have no solution and an under-constrained problem may produce many alternative solutions.
The first stage in constraint satisfaction is constraint propagation, where any dependencies between constraints are exploited to introduce more constraint and thus reduce the solution space. Then follows a search where variables are assigned values and matched against current constraints; this involves further constraint propagation and backtracking from failures. A solution is produced when a single set of values fits the final reduced set of constraints. An overconstrained problem will have no solution and an under-constrained problem may produce many alternative solutions.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
constraint satisfaction