Current Work
Current work on improving the algorithm has been done on three directions: defining different policies for choosing the branching literals; defining new data structures to make the algorithm faster, especially the part on unit propagation; and defining variants of the basic backtracking algorithm. The latter direction include non-chronological backtracking (aka. backjumping) and clause learning. These refinements describe a method of backtracking after reaching a conflict clause which "learns" the root causes (assignments to variables) of the conflict in order to avoid reaching the same conflict again.
A newer algorithm from 1990 is Stålmarck's method. Also since 1986 (reduced ordered) binary decision diagrams have also been used for SAT solving.
Read more about this topic: DPLL Algorithm
Famous quotes containing the words current and/or work:
“But there, where I have garnered up my heart,
Where either I must live or bear no life;
The fountain from the which my current runs
Or else dries up: to be discarded thence,
Or keep it as a cistern for foul toads
To knot and gender in!”
—William Shakespeare (1564–1616)
“The work was like peeling an onion. The outer skin came off with difficulty ... but in no time you’d be down to its innards, tears streaming from your eyes as more and more beautiful reductions became possible.”
—Edward Blishen (b. 1920)