Ìܼ¡
Why Adding More Constraints Makes a Problem Easier for Hill-climbing Algorithms: Analyzing Landscapes of CSPs
Summary
Background: Constraint Satisfaction Problem
Background: Complete Search Algorithm (Backtracking)
Background: Incomplete Search Algorithm (GSAT)
Background: Phase Transition
Performance of Incomplete Search Algorithm
Evaluation
Analyzing Landscapes of CSP
Algorithm
Solution Reachability
Ratio of Solution Reachable States
No. of Local Minima
Basin
No./Width of Basins
Conclusions
Future Works
Solvable/unsolvable Instances
|