Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

#### 4.8.2.2 Two-Stage Choice

An alternative is to split the choice of a variable-value pair into first choosing a variable to change and then choosing a value.

This algorithm maintains a priority queue of variables, where the weight of a variable is the number of conflicts in which it participates. At each time, the algorithm selects a variable with maximum weight. Once a variable has been chosen, it can be assigned a value that minimizes the number of conflicts. For each conflict that has its value changed as a result of this new assignment, the other variables participating in the conflict must have their weight changed.

The complexity of one step of this algorithm is *O( log n + r log n)*.
Compared to selecting the best variable-value pair, this does less work for each step and
so more steps are achievable for any fixed time period. However, the steps tend
to give less improvement, and so a trade-off exists between the number of
steps and the complexity per step that must be evaluated empirically.