Min-conflicts algorithm

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a min-conflicts algorithm is a <a href="/facts/Search_algorithm/eJuw0nyz">search algorithm</a> or heuristic method to solve <a href="/facts/Constraint_satisfaction_problem/oKCeIV2L">constraint satisfaction problems</a>.
One such algorithm is min-conflicts hill-climbing. Given an initial assignment of values to all the variables of a constraint satisfaction problem (with one or more constraints not satisfied), select a variable from the set of variables with conflicts violating one or more of its constraints. Assign to this variable a value that minimizes the number of conflicts (usually breaking ties randomly). Repeat this process of conflicted variable selection and min-conflict value assignment until a solution is found or a pre-selected maximum number of iterations is reached. If a solution is not found the algorithm can be restarted with a different initial assignment.
Because a constraint satisfaction problem can be interpreted as a <a href="/facts/Local_search_(optimization)/G1D2aHBz">local search problem</a> when all the variables have an assigned value (called a complete state), the min conflicts algorithm can be seen as a repair <a href="/facts/Heuristic_(computer_science)/PM2qkoa2">heuristic</a> that chooses the state with the minimum number of conflicts.

Min-conflicts algorithm open-in-new

Min-conflicts algorithm