dict.org

The DICT Development Group


Search for:
Search type:
Database:

Database copyright information
Server information
Wiki: Resources, links, and other information


1 definition found
 for constraint satisfaction
From The Free On-line Dictionary of Computing (18 March 2015) :

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

Questions or comments about this site? Contact webmaster@dict.org