質問

On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack all it says is "to the appropriate point". MiniSAT also uses a variant of the CDCL algorithm so I read this paper. What they seem to say is that you should backtrack until the learned clause is a unit clause. That is certainly clarification but it doesn't make sense to me. The last assignment is definitely going to be part of the learned conflict clause as far as I can tell (perhaps I am wrong here?) so when you backtrack one step you will immediately make the learned clause unit, the last assigned value will flip, and the algorithm will proceed exactly as DPLL without ever backtracking sufficiently far. Additionally the wikipedia page doesn't follow this rule, it backtracks much further as seems desirable.

How far is one supposed to backtrack?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top