Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
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.
