Tabu search for maximal constraint satisfaction problems(3)

{ The set of con gurations S is the set of all the complete assignments s de ned by s= f< Vi; vi> j Vi 2 X and vi 2 Di g. Clearly the cardinality of the search space S is equal to the product of the sizes of the domains, i.e. Qn jDij. i=1{ The cost f(s) of a con guration s is the number of constraints violated bys.