end if (5)选择一个未赋值的文字 (6)/*拆分 if DP(F[/1)=Yes then return Yes else return DP(F[OD) end if End/* dp * 可以看出,DP算法是对回溯算法的精化,其中应用了我们在前面提到的化简策略单元 子句规则和纯文字规则。前面已经介绍过,这些策略并不能在数量级上降低算法的时间复杂 度,但实验证明这些策略的应用可以极大的改善平均性能。其实,上面介绍的策略都可以应 用于SAT的求解,而且已经有了这方面的工作。 122SAT问题的并行算法 1并行化思路 通过我们在前面对串行DP算法的介绍可以看出,实际上DP算法仍然是利用深度优先 方法对可能的解空间做深度优先搜索,这样我们仍然可以把这个解空间看成一棵二叉树。而 它与回溯搜索算法的区别仅仅在于它利用了SAT的一些性质巧妙的找到了一些仅有一种赋 值可能的文字,这样就有效地减少了搜索开销。同时在搜索一棵子树时,对某个文字的赋值 可能导致新的单元子句的产生,这样,从平均意义上考虑,对这一性质的反复利用可以极大 地加快搜索速度。容易知道,对于寻找单元子句和纯文字的工作是在多项式时间内完成的, 因此我们可以由主进程预先把CNF的所有单元子句和纯文字找出来,对它们分别赋上可能 使CNF得到满足的值,并按照某种策略选取n个文字对他们预先赋值,共得到2组解。然 后把这些信息分别发送给各个从进程进行计算,并收集运算结果。这样既避免了各个从进程 重复寻找单元子句和纯文字,又有可能通过对选出的n个文字的赋值产生了新的单元子句, 从而加快了整个程序的搜索速度。 2并行DP算法 算法16.4SAT问题的并行DP算法 输入:合取范式F 输出:F是否可满足 (1)主进程算法 procedure PDPMaster(F (1)找出n个文字,并初始化任务队列 (2)j=0 (3)向每个从进程发送一个任务 (4) while true do (4.1)某个从进程p接收结果 (4.2) if result= true then (i)向所有从进程发送终止信号4 end if (5) 选择一个未赋值的文字 l (6) /* 拆分 */ if DP(F [l/1]) = Yes then return Yes else return DP(F [l/0]) end if End /* DP */ 可以看出，DP 算法是对回溯算法的精化，其中应用了我们在前面提到的化简策略单元 子句规则和纯文字规则。前面已经介绍过，这些策略并不能在数量级上降低算法的时间复杂 度，但实验证明这些策略的应用可以极大的改善平均性能。其实，上面介绍的策略都可以应 用于 SAT 的求解，而且已经有了这方面的工作。 1.2.2 SAT 问题的并行算法 1.并行化思路 通过我们在前面对串行 DP 算法的介绍可以看出，实际上 DP 算法仍然是利用深度优先 方法对可能的解空间做深度优先搜索，这样我们仍然可以把这个解空间看成一棵二叉树。而 它与回溯搜索算法的区别仅仅在于它利用了 SAT 的一些性质巧妙的找到了一些仅有一种赋 值可能的文字，这样就有效地减少了搜索开销。同时在搜索一棵子树时，对某个文字的赋值 可能导致新的单元子句的产生，这样，从平均意义上考虑，对这一性质的反复利用可以极大 地加快搜索速度。容易知道，对于寻找单元子句和纯文字的工作是在多项式时间内完成的， 因此我们可以由主进程预先把 CNF 的所有单元子句和纯文字找出来，对它们分别赋上可能 使 CNF 得到满足的值，并按照某种策略选取 n 个文字对他们预先赋值，共得到 2 n 组解。然 后把这些信息分别发送给各个从进程进行计算，并收集运算结果。这样既避免了各个从进程 重复寻找单元子句和纯文字，又有可能通过对选出的 n 个文字的赋值产生了新的单元子句， 从而加快了整个程序的搜索速度。 2.并行 DP 算法 算法 16.4 SAT 问题的并行 DP 算法 输入：合取范式 F。 输出：F 是否可满足。 （1）主进程算法 procedure PDPMaster(F) Begin （1）找出 n 个文字，并初始化任务队列 （2）j = 0 （3）向每个从进程发送一个任务 （4）while true do （4.1）某个从进程 pi 接收结果 （4.2）if result = true then （i）向所有从进程发送终止信号