Heuristics for DPLL
We need variable ordering heuristics
- can easily make the difference between success/failure
Tradeoff between simplicity and effectiveness
Three very simple variable ordering heuristics
- lexicographic: choose A before B before C before …
- random: choose a random variable
- first occurrence: choose first variable in first clause
Pros: all very easy to implement
Cons: ineffective except on very small or easy problems