constraint satisfaction

Computing Dictionary

constraint satisfaction definition

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)
The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: constraint logic programming
Next Definition: constraintive
More from Thesaurus.com
Synonyms and Antonyms for constraint satisfaction
More from Reference.com
Search for articles containing constraint satisfaction
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature