L13: Combining Search and Propagation Flashcards
Fundamentally, how do systematic solvers work?
- Guess an assignment.
- Propagate consequences of that assignment.
- If all is well (and not done) go to 1.
What is forward checking?
Forward checking is a strategy used in constraint satisfaction problems to efficiently prune the search space by checking the remaining domain values of unassigned variables after a variable is assigned a value.
After an assignment to xi, revise arcs from every future variable to xi once.
I.e., enforce local arc consistency on a subset of the arcs.
Forward checking guarantees to find a solution if it exists.
What are the advantages of forward checking?
We can spot dead ends earlier, and reduce the space to search (and hence the search time).
Why doesn’t forward checking need to check backwards?
Consider a past variable xp and the current variable xc.
When xp was assigned, arc(xc, xp) was revised.
This removed all values in the domain of xc incompatible with the assignment to xp.
When later considering an assignment to xc, all possible assignments are guaranteed to be compatible with the assignment to xp.
When does forward checking beat backtracking?
If there is a constraint that cannot be satisfied, the backtracking in forward checking is more effective as it goes back potentially multiple levels of depth to satisfy the constraint.
Forward checking is guaranteed to explore a search tree smaller than or equal to backtracking. This saves the search time compared to backtracking whenever there is a wipeout of a future variable.
How do we enforce arc consistency?
We need an algorithm that efficiently re- revises arcs as necessary.
What is AC3?
It is an algorithm of effectively maintaining arc consistency.
In AC3, when are arcs added to the queue?
If there has been an arc(xi, xj) where the domain of i has been changed, all arcs with xi are added to the queue.
Support is bi-directional.
If a value is supported on arc(x1,x2), then it is supporting some value(s) on arc(x2,x1)
Conversely: if a value is not supported on arc(x1,x2), then it is supporting no values on arc(x2,x1)
No need to revise arc(x2,x1) after revising arc(x1,x2)
What is the time complexity of AC3?
AC3 has worst-case time complexity of O(ed^3).
Where:
- e is the number of edges in the constraint graph.
- d is the maximum domain size.
Each arc(xi, xj) is revised if it enters the queue. This only happens if Dj loses a value.
Each arc can enter the queue/be revised at most d times. There are 2e arcs, so Revise() is executed O(ed) times.
Complexity of Revise() is O(d^2).
Compare forward checking with arc consistency.
Full arc consistency is stronger than mere forward checking.
