(7th-May-2020)
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.
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.
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.
Comments