Dead-End Driven Learning

Daniel Frost, Rina Dechter

The paper evaluates the effectiveness of learning for speeding up the solution of constraint satisfaction problems. It extends previous work (Dechter 1990) by introducing a new and powerful variant of learning and by presenting an extensive empirical study on much larger and more difficult problem instances. Our results show that learning can speed up backjumping when using either a fixed or dynamic variable ordering. However, the improvement with a dynamic variable ordering is not as great, and for some classes of problems learning is helpful only when a limit is placed on the size of new constraints learned.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.