L16: AC3 Flashcards
What is Geelen’s promise?
Having chose n the most constrained variable, choose the value that promises the best chance of finding a solution.
That is, the least constraining value by a different measure from min-conflicts.
When does value assignment order matter?
When searching for one solution, clearly.
By assigning the ‘right’ value each time we will reach a solution in linear steps.
Optimisation: the sooner we find a better solution than the current best, the sooner we can prune more of the search tree.
Does the value assignment order matter if we do not have any solutions, or we want to identify all solutions?
In d-way branching, if w have to try all value assignments to exhaust the search space, the order doesn’t matter.
However in binary branching, it can reduce the search tree well.
E.g. If there is no solution, both assignments x = 1 and x ≠ 1 will fail. However with d-way branching, all the values will be explored before concluding that there is no solution.
Where can there be inefficiency in AC3?
We are adding arcs to the queue where there is no further propagation.
How can we anticipate whether an arc will be propagated?
Use an optimal arc consistency algorithm such as AC4.
Why is AC3 sub-optimal?
AC3 wastes a considerable effort in adding arcs onto the queue whose revision will not lead to any domain pruning. This is the root cause of its sub-optimal time complexity of O(ed^3) where e is the number of edges in the constraint graph, and d is the maximum domain size.
It is possible to produce an optimal arc consistency algorithm.
Explain the granularity of AC3.
AC3 is smart about which arcs might need to be revised (coarse-grained). However, it does not know how the support of individual domain elements has been affected by a revision. If we have this fine-grained knowledge, we can save some work.
What is a coarse-grained algorithm?
Coarse-grained algorithms have a queue Q of arcs. When revise is called for an arc, it doesn’t know which value(s) were deleted.
What is a fine-grained algorithm?
Fine-grained algorithms have a list of deleted values L. When revising an arc, it knows why (specifically it knows which values were deleted).
What is AC4?
AC4 is a fine-grained algorithm. For each domain element, we know how many supports it has, and for which other elements it provides support.
What is the time complexity of AC4?
Worst case: O(ed^2)
- e is the number of edges in the constraint graph
- d is the maximum domain size
Initialisation
- O(ed^2)
- For each arc, double-nested loop of length d
Propagation
- At most O(ed) counters, each decremented at most d times.
This is worst-case optimal.
What is the space complexity of AC4?
Worst case: O(ed^2)
Initialisation
- At most ed^2 additions to S.
- The M array takes O(nd) space
- The counters array takes O(ed) space
AC3 has a worst-case space complexity of O(e+nd)
- This is optimal: require at least this much just to represent constraint graph and domains.
Compare AC3 and AC4.
AC4 worst-case time is better than AC3.
But AC4 always reaches this worst (initialisation of data structures), so people often prefer AC3 to AC4 in practice.
AC3 has a better worst-case space complexity.
Is there a better algorithm than AC3 and AC4?
AC2001/3.1
What is the time complexity of AC2001/3.1?
Worst-case: O(ed^2)
- e is the number of edges in the constraint graph
- d is the maximum domain size
Each arc(xi, xk) is revised at most d times (since Dk can lose at most d elements).
We traverse Dk (size d) once.
