资料来源 : Free On-Line Dictionary of Computing

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)} (Tad
        Hogg, {XEROX PARC}).
     
        (1995-02-15)