constraint satisfaction
<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 tasks.
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.
Phase transitions in search (Tad Hogg, XEROX PARC).
(1995-02-15)
Nearby terms:
ConstraintLisp « Constraint Logic Programming «
CONSTRAINTS « constraint satisfaction »
constructed type » constructive » Constructive Cost
Model
|