Summary
Motivation: explain paradoxical result of the performance of hill-climbing algorithms (e.g., GSAT), i.e., adding more constraints (so that a problem has less solutions) makes a problem easier beyond the phase transition region
Method: exhaustively analyze the landscape of CSP created by the evaluation value
Result:
- No. of local minima decreases by adding constraints.
- A set of interconnected local minima (basin) is divided into smaller regions.