Memoization as a very conservative form of no-good learning

• No-goods are compound assignments that cannot be part of a solution

• Memos are subsets of variables at some level i that cannot be active together

• • Each m-sized memo corresponds to the conjunction of dm no-goods
  • There are O((d+2)n) no-goods but only O(l*2n/l)memos
  • Only the memos from the current level are checked during search

Previous slide

Next slide

Back to first slide

View graphic version