constraint satisfaction

1 definition found

constraint satisfaction - Free On-line Dictionary of Computing (26 May 2007) :

  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 (ftp://parcftp.xerox.com/pub/dynamics/constraints.html)
      (Tad
     Hogg, XEROX PARC).
  
     (1995-02-15)