Min-conflicts Algorithm - Algorithm

Algorithm

function MIN-CONFLICTS(csp,max_steps) returns a solution or failure inputs: csp, a constraint satisfaction problem max_steps,the number of steps allowed before giving up current<-- an initial assignment for csp for i=1 to max_steps do if current is a solution of csp then return current var<-- a randomly chosen, conflicted variable from VARIABLES value<-- the value v for var that minimizes CONFLICTS(var,v,current,csp) set var = value in current return failure

Although not specified in the algorithm, a good initial assignment can be critical for quickly approaching a solution. Use a greedy algorithm with some level of randomness and allow variable assignment to break constraints when no other assignment will suffice. The randomness helps min-conflicts avoid local minima created by the greedy algorithm's initial assignment. In fact, Constraint Satisfaction Problems that respond best to a min-conflicts solution do well where a greedy algorithm almost solves the problem. Map coloring problems do poorly with Greedy Algorithm as well as Min-Conflicts. Sub areas of the map tend to hold their colors stable and min conflicts cannot hill climb to break out of the local minimum. The CONFLICTS function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known.