Why adding more constraints madkes a problem easier for hill climbing algorithms: analyzing landscapes of CSPs

摘要

It is well known that constraint stisfaction problem (CSPs) in the phase transition region are most difficult for complete search algorithms. On the other hand, for incomplete hill-climbind algorithm,s problems in the phase transition region are more difficult than problems beyond the phase transition region, ile.., more constrained problems. This result seems somewhat unnatural since these more constrained probolems have fewer solutions than the phase transition problems.