L15: Variable Heuristics Flashcards
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 variables in ascending order
What are some operations we can order heuristically?
- Variable assignment order.
- Value assignment order.
- Constraint checking order.
What are dynamic heuristics?
- Examine the state of the problem during the search
- Decide on the ‘best’ variable/value to assign next
E.g.
- ’Smallest domain’ variable ordering (Affected by FC/MAC propagation, which differs based on the assignments made)
- ‘Min-conflicts’ value ordering
How do we know which type of heuristic to choose?
- 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 first ordering?
For each variable, the first value we assign that is compatible with the past assignments is part of the solution.
What is second ordering?
Because of the variable assignment order, we make assignments that ‘look good’ but turn out to have no solutions and backtracking is required. (e.g. thrashing- repeated failure for the same reason)
How can we look at static variable heuristics?
Using a graph that represents the constraints
What is a primal graph?
The primal graph has an edge between two nodes if they are in a constraint together (unlike the constraints graph where each edge represents a constraint)
What is a hypergraph?
A graph that describes an area rather than just an edge between 2 nodes.
What is maximum degree ordering?
Order variables in decreasing order of their degrees in the graph (break ties arbitrarily).
What is the degree of a variable?
How many edges the variable has
How does maximum degree fit with the rationale of making hard choices first?
Variables in a lot of constraints may be highly constrained. However they may not, constraints vary in tightness.
Highly constrained may be the hardest choices.
What is maximum cardinality ordering?
- Select the first variable arbitrarily
- Repeat until there are no more variables: append to the order a variable connected to the largest group among those already selected.
We want to prioritise the nodes with the most constraints that are related to past variables.
E.g., when picking node 4, we would prefer to pick a node with constraints to nodes 1, 2, 3 as much as possible.
How does maximum cardinality fit with the rationale of making hard choices first?
After assigning some variables, the next hard choice is the one most constrained by the existing assignment (after all we need to make choices compatible with the existing assignment).
What is the width at an ordered node?
Number of arcs/edges linking back to a previous variable in the ordering.
