CONSTRAINT SATISFACTION
\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]\
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
Word of the day
dust storm
- a windstorm that lifts up clouds of dust or sand a windstorm that lifts up clouds dust or sand; "it was the kind of duster not experienced in years"