Index
Weak-commitment Search for Solving Constraint Satisfaction Problems
Summary
Constraint Satisfaction Problem (CSP)
Backtracking Algorithm
Min-conflict Backtracking [Minton, et al, 92]
Drawbacks of Min-conflict Backtracking
Iterative Improvement Algorithms
Drawbacks of Iterative Improvement Algorithms
Weak-commitment Search Algorithm
Example of Algorithm Execution
The Advantages of the Weak-commitment Search
Evaluation Result (n-queens)
Evaluation Result (graph coloring)
Probabilistic Model
Algorithm Complexity
Conclusions
Future Works
Evaluation Result (3 SAT)
|