\kənstɹˈe͡ɪnt sˌatɪsfˈakʃən], \kənstɹˈeɪnt sˌatɪsfˈakʃən], \k_ə_n_s_t_ɹ_ˈeɪ_n_t s_ˌa_t_ɪ_s_f_ˈa_k_ʃ_ə_n]\
Definitions of CONSTRAINT SATISFACTION
Sort: Oldest first
The process of assigning values to variableswhile meeting certain requirements or "constraints". Forexample, in graph colouring, a node is a variable, thecolour assigned to it is its value and a link between twonodes represents the constraint that those two nodes must notbe assigned the same colour. In scheduling, constraintsapply to such variables as the starting and ending times fortasks.The Simplex method is one well known technique for solvingnumerical constraints.The search difficulty of constraint satisfaction problems canbe determined on average from knowledge of easily computedstructural properties of the problems. In fact, hardinstances of NP-complete problems are concentrated near anabrupt transition between under- and over-constrainedproblems. This transition is analogous to phase transitionsin physical systems and offers a way to estimate the likelydifficulty of a constraint problem before attempting to solveit with search.Phase transitions in search(ftp://parcftp.xerox.com/pub/dynamics/constraints.html) (TadHogg, XEROX PARC).
By Denis Howe