Min-conflicts algorithm
In computer science, the min-conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems. Given an initial assignment of values to all the variables of a constraint satisfaction problem, the algorithm randomly selects a variable from the set of variables with conflicts violating one or more its constraints. Then it assigns to this variable the value that minimizes the number of conflicts. If there is more than one value with a minimum number of conflicts, it chooses one randomly. This process of random variable selection and min-conflict value assignment is iterated until a solution is found or a pre-selected maximum number of iterations is reached.
- Comment
- enIn computer science, the min-conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems. Given an initial assignment of values to all the variables of a constraint satisfaction problem, the algorithm randomly selects a variable from the set of variables with conflicts violating one or more its constraints. Then it assigns to this variable the value that minimizes the number of conflicts. If there is more than one value with a minimum number of conflicts, it chooses one randomly. This process of random variable selection and min-conflict value assignment is iterated until a solution is found or a pre-selected maximum number of iterations is reached.
- Depiction
- Has abstract
- enIn computer science, the min-conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems. Given an initial assignment of values to all the variables of a constraint satisfaction problem, the algorithm randomly selects a variable from the set of variables with conflicts violating one or more its constraints. Then it assigns to this variable the value that minimizes the number of conflicts. If there is more than one value with a minimum number of conflicts, it chooses one randomly. This process of random variable selection and min-conflict value assignment is iterated until a solution is found or a pre-selected maximum number of iterations is reached. 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.
- Hypernym
- Algorithm
- Is primary topic of
- Min-conflicts algorithm
- Label
- enMin-conflicts algorithm
- Link from a Wikipage to an external page
- catalogue.nla.gov.au/Record/4057689
- Link from a Wikipage to another Wikipage
- Artificial Intelligence: A Modern Approach
- Category:Constraint programming
- Computer science
- Constraint satisfaction problem
- Discrete optimization
- Eight queens
- File:8queensminconflict.gif
- Greedy algorithm
- Guided Local Search
- Heuristic (computer science)
- Hubble Space Telescope
- Local search (optimization)
- Map coloring
- Peter Norvig
- Search algorithm
- Space Telescope European Coordinating Facility
- Space Telescope Science Institute
- Stuart J. Russell
- Warnsdorff's algorithm
- SameAs
- 4rsfN
- m.06d0rr
- Q6862473
- Subject
- Category:Constraint programming
- Thumbnail
- WasDerivedFrom
- Min-conflicts algorithm?oldid=1053522896&ns=0
- WikiPageLength
- 7962
- Wikipage page ID
- 2000174
- Wikipage revision ID
- 1053522896
- WikiPageUsesTemplate
- Template:Mono
- Template:Reflist
- Template:Short description
