Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
4.8.2.3 Any Conflict
An even simpler alternative, instead of choosing the best step, is to select any variable participating in a conflict and change its value. At each step, one of the variables involved in a violated constraint is selected at random. The algorithm assigns to that variable one of the values that minimizes the number of violated constraints.
To implement this alternative, we require a data structure to represent the set C of variables involved in a conflict. This data structure should be designed for quick selection of a random member of C. When a variable X has its value changed, each constraint in which X is involved is checked. For each such constraint that has become violated, all of the variables involved in the constraint are added to C. For each such constraint that is no longer violated, those variables involved in that constraint, but not involved in another violated constraint, are removed from C. One way to check whether a variable is involved in another conflict is to maintain a count of the number of conflicts for each variable, which is incremented when a constraint becomes violated and decremented when a constraint is no longer violated.
Each of the preceding algorithms can be combined with random steps, random restarts, and a tabu mechanism.
