Why Adding More Constraints Makes a Problem Easier for Hill-climbing
Algorithms: Analyzing Landscapes of CSPs
Conference on Principles and Practice of Constraint Programming (CP-97),
It is well known that constraint satisfaction problems (CSPs) in the phase
transition region are most
difficult for complete search algorithms.
On the other hand, for incomplete hill-climbing algorithms,
problems in the phase transition region are more difficult than
problems beyond the phase transition region, i.e., more
This result seems somewhat unnatural since
these more constrained problems have fewer solutions than the phase
In this paper, we clarify the cause of this paradoxical phenomenon by
exhaustively analyzing the state-space landscape of CSPs,
which is formed by the evaluation values of states.
The analyses show that by adding more constraints,
while the number of solutions decreases, the number of local-minima
also decreases, thus the number of states that are reachable to
Furthermore, the analyses clarify that the decrease in
local-minima is caused by
a set of interconnected local-minima
(basin) being divided into smaller regions by adding more constraints.