Artificial Intelligence
Search: the story so far
Example Search Problem: SAT
It’s the same thing
Depth First Search for SAT
Unit Propagation
Depth First + Unit Propagation
Davis-Putnam
Algorithm DPLL (clauses)
DPLL success
It’s the same thing (again)
Heuristics for DPLL
How can we design better heuristics
Three Design Principles
Most Constrained First
Satisfaction Hypothesis
Simplification Hypothesis
Conclusions
Email: ipg@dcs.st-and.ac.uk
Home Page: http://www.dcs.st-and.ac.uk/~ipg
Download presentation source