Lesson plan
Min-conflicts algorithm
In computer science, a min-conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems. 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 local search problem when all the variables have an assigned value (called a complete state), the min conflicts algorithm can be seen as a repair heuristic that chooses the state with the minimum number of conflicts.
Article summary
In computer science, a min-conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems. 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 local search problem when all the variables have an assigned value (called a complete state), the min conflicts algorithm can be seen as a repair heuristic that chooses the state with the minimum number of conflicts.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.