L14: MAC and more branching Flashcards
What is d-way branching?
In d-way branching, each branch under a parent node represents the assignment of one of d domain values from the domain of a particular variable.
What is 2-way branching?
In 2-way branching, try extending partial assignment with x = v first. If no solution, remove v from consideration.
Compare 2-way with d-way branching.
2-way branching can identify dead ends more quickly, especially in cases where there are no solutions.
After a right-branch it is possible to select a different variable to assign.
How can we use heuristics for CSP/COPs?
“Rules of thumb” that, if we follow them, are expected to lead to an improvement in general.
Operations we can order heuristically:
1. Variable assignment order.
2. Value assignment order.
3. Constraint checking/propagation order.
What are static heuristics?
Order in which variables/values selected/assigned chosen before search.
- Order is set before search starts.
- Order is fixed for entire search.
E.g.
- Assign variables in order x1, x2, x3
- Assign values in ascending order
What are dynamic heuristics?
Examine the state of the problem during search.
Decide on “best” variable/value to assign next.
E.g.
- “Smallest-domain” variable ordering. (Affected by FC/MAC propagation, which differs based on the assignment made.)
- “Min-conflicts” value ordering.
What is the significance of variable assignment order?
It can have a substantial effect on size of search tree.
What is thrashing?
Repeated failure for the same reason.
This is because we are not getting to the ‘root’ cause of the problem.
E.g. in the case of searching for a solution: there is pointless search over a set of variables.
Do variable ordering heuristics matter when using FC?
Yes.
Without variable ordering, there can still be lots of thrashing.
Do variable ordering heuristics matter when using MAC?
Yes.
Without variable ordering, there can still be lots of thrashing.
What is the rationale for heuristics?
Make the most difficult choice first (variables).
Have the most far-reaching consequences for the rest of the problem.
Narrows down easy choices.
If we make the easy choices first, we can paint ourselves into a corner, as in the previous example.
For the most difficult choice choose the option most likely to succeed (values).
What is the basic idea of MAC?
Start by making the problem (globally) arc consistent.
After every assignment, re-establish (global) arc consistency.
What are the benefits of MAC?
Spots dead-ends earlier than FC, so less search.
We know how to enforce AC efficiently, so cost per search node is still small.
How do we enforce AC during search?
Needs to establish global arc consistency before beginning search.
We assign a value to the x1 =1 first variable.
It is not necessary to revise all arcs at every node on a branch of the search tree.
After every left branch xi = di, initialise the queue with the consequences of removing all but di from Di. Propagate these changes to re-establish arc consistency.
The right branch xi ≠ di is handled similarly.
