Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
4.8.2.1 Most Improving Step
The first method is to always select the variable-value pair that makes the best improvement. The naive way of doing this is to linearly scan the variables; for each value of each variable, determine how many fewer constraints would be violated with this assignment compared to the current assignment to all variables, then select one of the variable-value pairs that results in the best improvement, even if that improvement is negative. The complexity of one step is O(ndr), where n is the number of variables, d is the average domain size, and r is the number of neighbors of an assignment.
A more sophisticated alternative is to have a priority queue of variable-value pairs. For any variable X, and value v in the domain of X such that X is not assigned to v in the current assignment, the pair ⟨X,v⟩ would be in the priority queue; the weight of the pair is the evaluation of the current total assignment minus the evaluation of the total assignment if X, instead, had value v. That is, it maintains the change in the evaluation for each alternate value. At each stage, the algorithm selects a value with minimum weight, which is the neighbor that gives the biggest improvement.
Once a variable X has been given a new value, the weights of all variables that participate in a constraint that has been made satisfied or unsatisfied by the new assignment to X must have their weights changed and must be reinserted into the priority queue.
The complexity of one step of this algorithm is O( log nd + rd log nd), where n is the number of variables, d is the average domain size, and r is the number of neighbors of an assignment.
This algorithm spends much time maintaining the data structures to ensure that the most improving step is taken at each time.
