Solution Based Backjumping

• Thrashing can occur just as in SAT, and likely worse

• Can implement Prosserís CBJ

  • but only applies to branches that fail

• We need a new form of backjumping after successes

  • invented in Genova but named in St Andrews

• Remember a single success is not a solution

  • we need a strategy
  • we can recycle elements of a strategy
  • if a universal variable is not used in a solutionÖ

    • Ö we can backjump over it when backtracking

Previous slide

Next slide

Back to first slide

View graphic version