Min-conflicts algorithm

From Wikipedia, the free encyclopedia

The min conflicts algorithm is a search algorithm to solve constraint satisfaction problems (CSP problems).

It assigns random values to all the variables of a CSP. Then it selects randomly a variable, whose value conflicts with any constraint of the CSP. Then it assigns to this variable the value with the minimum conflicts. If there are more than one minimum, it chooses one among them randomly. After that, a new iteration starts again until a solution is found or a preselected maximum number of iterations is reached.

Because a CSP can be interpreted as a local search problem when all the variables have assigned a value (complete states), the min conflicts algorithm can be seen as a heuristic that chooses the state with the minimum number of conflicts.

[edit] 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 assingment 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[csp]
       value<-- the value v for var that minimizes CONFLICTS(var,v,current,csp)
       set var = value in current
 return failure