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

#### 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.