基于树 二叉树的回溯搜索算法（DPLL）

1）全称：Davis-Putnam-Logemann-Loveland
2）思想：基于树/二叉树的回溯搜索算法，主要基于两种策略。

• 单子句规则：如果一个CNF范式中存在单子句L（含有一个文字的子句），取L为真值。通过L的值，遍历其他的子句：
  如果某个子句中含有L，则将这个子句从范式中去掉（子句没了）
  如果某个子句中含有-L（L的非），则将-L从这个子句中去掉（文字没了）
  处理完之后，如果范式为空，则该范式为真；如果范式中含有空子句，则该范式为假。
• 分裂策略：如果一个范式S中不存在单子句。则按照某种方式选取一个变元v，假设v为真值和假值，然后重复单子句规则。（算法的复杂度和是否高效取决于选择变元的策略）

//伪代码：
bool DPLL(范式S){while(S中有单子句L){for(子句P in S){if(P中有L) 去掉P;else if(P中有-L) 去掉-L;}for循环执行完毕之后，S化简为S1if(S1 为空) return TRUE;else if(S1 中含有空子句) return FLASE;}按照某种策略选择变元v;if(DPLL(S∪v)) return TRUE;//递归回溯部分else return DPLL(S∪-v);
}

注意：既然是递归算法，自然要注意几个重要的点。其中有一个就是要记得你写的递归是否需要回溯。如果需要回溯，那些中间变量以及标记变量都需要及时回溯。（在传指针的时候尤其需要注意！！！）