Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sav08:advanced_sat_solving_techniques [2008/03/12 21:40] vkuncak |
sav08:advanced_sat_solving_techniques [2008/03/13 10:45] vkuncak |
||
|---|---|---|---|
| Line 45: | Line 45: | ||
| Need efficient data structures: | Need efficient data structures: | ||
| + | * counters: simple, need many updates | ||
| * head/tail list | * head/tail list | ||
| - | * two-literal watching | + | * two-literal watching: each var has list of unassigned literals, do search to see if there are other literals to watch in clause |
| + | * invariant: each non-conflicting clause has at least one watched literal, but not all literals need to be watched | ||
| + | * no need to do anything on backtrack | ||
| - | Other mechanisms less important: e.g. propagating equivalences. | + | Mechanisms other than unit propagation are less important: e.g. propagating equivalences. |
| ===== Conflict Analysis and Lemma Learning - analyze_conflict() ===== | ===== Conflict Analysis and Lemma Learning - analyze_conflict() ===== | ||