Search in: Word
Vietnamese keyboard: Off
Virtual keyboard: Show
Computing (FOLDOC) dictionary
constraint satisfaction
Jump to user comments
application The process of assigning values to variables
while meeting certain requirements or "constraints". For
example, in graph colouring, a node is a variable, the
colour assigned to it is its value and a link between two
nodes represents the constraint that those two nodes must not
be assigned the same colour. In scheduling, constraints
apply to such variables as the starting and ending times for
The Simplex method is one well known technique for solving
numerical constraints.
The search difficulty of constraint satisfaction problems can
be determined on average from knowledge of easily computed
structural properties of the problems. In fact, hard
instances of NP-complete problems are concentrated near an
abrupt transition between under- and over-constrained
problems. This transition is analogous to phase transitions
in physical systems and offers a way to estimate the likely
difficulty of a constraint problem before attempting to solve
it with search.