L17: Loopback Schemes, Backjumping

Question 1

What is a look-ahead scheme?

Answer 1

Invoked when an algorithm is preparing to extend the current partial assignment.
Include:
- Variable/value ordering heuristics.
- Propagation schemes, such as MAC, FC.

Question 2

What is a look-back scheme?

Answer 2

Invoked when dead-end encountered, algorithm prepares for backtracking step.

There are 2 types of look-back schemes:
- Conflict-recording
- Backjumping

Question 3

How do we classify backtrack?

Answer 3

Backtrack is both the simplest lookahead scheme:
- Just check against past assignments.

And the simplest look-back scheme:
- Backtrack chronologically to the previous variable.

Question 4

Reminder: What is thrashing?

Answer 4

Repeated failure for the same reason.
We can reduce thrashing with variable ordering- but generally the ‘right’ ordering is unknown.

Question 5

What is backjumping?

Answer 5

Replace chronological backtracking with a
jump back to the variable that is causing the dead-end.
How this variable is determined depends on the look-forward scheme (e.g. BT vs FC).

Question 6

What is the limitation of backjumping?

Answer 6

After one jump, backjumping resorts to chronological backtracking.
This is because it jups back to the maximum level checked against. When an assignment to Xdepth is consistent, checks must have been made up to Xdepth - 1.

Question 7

Why do we not jump back to the maximum level failed against?

Answer 7

This leads to incompleteness, meaning we may miss the solution.

Question 8

What is conflict-directed backjumping?

Answer 8

When trying assignments to xk, maintain the set of assignments failed against.
When jumping back from xk to xi, combine their conflict sets.
- Avoids forgetting other assignments that were conflicting with xk.
- Allows multiple backward jumps.