中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（实验）组合优化.doc_大学文库

3 1.2 SAT 问题 1.2.1 SAT 问题及其串行算法 1.SAT 问题描述所谓可满足性问题（Satisfiability Problem）即 SAT 问题，其定义为：对于一个命题逻辑公式，是否存在对其变元的一个真值赋值公式使之成立。这个问题在许多领域都有着非常重要的意义，而且对其快速求解算法的研究成为计算机科学的核心课题之一。例如在机器定理证明领域，某命题是否是一个相容的公理集合的推论，这个问题归结为该命题的反命题与该公理集合一起是否是不可满足的。特别是 1971 年 Cook 首次证明了 SAT 是 NP-完全的，从而大量的计算问题都可以归结到 SAT。正是由于 SAT 重要的理论和应用地位，众多学者对它进行了广泛而深入的研究。由命题逻辑知识可以知道，任何命题逻辑公式都逻辑等价与一个合取范式(Conjunctive Normal Form，简写为 CNF),因此本文只讨论 CNF 的 SAT 求解问题。下面给出几种常见的 SAT 问题化简策略，以下均假定 F 是 CNF 范式：①单元子句规则：若 C=｛L｝是 F 的子句，则 F 变为 F’=F[F/1]；②纯文字规则：若文字 L 出现在 F 中，而  L 不出现 F 中，则 L 称为 F 的纯文字。F 变为 F’=F[F/1]；③重言子句规则：若 C∈F 且 C 是重言子句，则从 F 中删去 C 得 F’=F-C；④两次出现规则：若 L∈C1， L∈C2，且 L 和  L 都不在其它子句中出现，则将 C1 ，C2 合并为 C’=( C1-｛L｝)∪( C2-｛  L｝)，F 变为 F’=F- ｛C1, C2｝∪｛C’｝；⑤包含规则：若 C1 ，C2是 F 的子句，且 C1∈C2，则 F 中删去 C2，得 F’=F-｛C2｝。 2.SAT 问题串行算法 SAT 问题的 DP 算法是由 M.Davis 和 H.Putnam 于 1960 年首次提出[2]，现在已经成为最著名的 SAT 算法，其描述如下：算法 16.3 SAT 问题的 DP 算法输入：合取范式 F。输出：F 是否可满足。 procedure DP(F) Begin (1) if F 为空公式 then return Yes end if (2) if F 包含一个空子句 then return No end if (3) if F 包含一个子句{l} then /* 单元子句规则 */ return DP(F[l/1]) end if (4) if F 包含一个文字 l，但不包含  l then /* 纯文字规则 */ return DP(F[l/1])

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）向所有从进程发送终止信号

6 1.3 装箱问题 1.3.1 装箱问题及其串行算法经典的一维装箱问题 (Bin Packing Problem) 是指，给定 n 件物品的序列 1 2 , , , L a a a n n =  ，物品 a (1 i n) i   的大小 ( )(0,1] ai s ，要求将这些物品装入单位容量 1 的箱子 1 2 , , , B B B m 中，使得每个箱子中的物品大小之和不超过 1，并使所使用的箱子数目 m 最小。下次适应算法（Next Fit Algorithm）是最早提出的、最简单的一个在线算法，[Joh73] 首次仔细分析了下次适应算法的最坏情况性能。下次适应算法维持一个当前打开的箱子，它依序处理输入物品，当物品到达时检查该物品能否放入这个当前打开的箱子中，若能则放入；否则把物品放入一个新的箱子中，并把这个新箱子作为当前打开的箱子。算法描述如下：算法 16.5 装箱问题的下次适应算法输入：输入物品序列 1 2 , , , L a a a =  n 。输出：使用的箱子数目 m，各装入物品的箱子 1 2 , , , P B B B =  m 。 procedure NextFit Begin （1）s(B) = 1 /* 初始化当前打开的箱子 B，令 B 已满 */ （2）m = 0 /* 使用箱子计数 */ （3）for i = 1 to n do if s(ai) + s(B)  1 then （i） s(B) = s(B) + s(ai) /* 把 ai 放入 B 中 */ else （i） m = m + 1 /* 使用的箱子数加一 */ （ii） B = Bm /* 新打开箱子 Bm */ （iii）s(B) = s(ai) /* 把 ai 放入 B 中 */ end if end for End /* NextFit */ 1.3.2 装箱问题的并行算法算法 16.5 使用一遍扫描物品序列来实现，本身具有固有的顺序性，其时间复杂度为 O(n)。我们使用平衡树和倍增技术对其进行并行化。首先利用前缀和算法建立一个链表簇，令 A[i] 为输入物品序列中第 i 件物品的大小, 如果链表指针由 A[j] 指向 A[k] ，则表示 A[j]+A[j+1]+…+A[k]>1 且 A[j]+A[j+1]+…+A[k-1]1；其后利用倍增技术计算以 A[1]为头的链表的长度，而以 A(1)为头的链表的长度即是下次适应算法所使用的箱子数目。接下来利用在上一步骤中产生的中间数据反向建立一棵二叉树，使该二叉树的叶节点恰好是下次适应算法在各箱子中放入的第一个物品的序号；最后，根据各箱子中放入的第一个物品的序号，使

10 MPI 源程序请参见所附光盘。 1.5 TSP 问题 1.5.1 TSP 问题及其串行算法 TSP 问题（Traveling-Salesman Problem）可描述为：货郎到各村去卖货，再回到出发处，每村都要经过且仅经过一次，为其设计一种路线，使得所用旅行售货的时间最短。 TSP 问题至今还没有有效的算法，是当今图论上的一大难题。目前只能给出近似算法，其中之一是所谓“改良圈算法”，即已知 1 2 1 ... v v v v v 是 G 的 Hamilton 圈，用下面的算法把它的权减小：算法 16.9 TSP 问题的改良圈算法输入：任意的一个 Hamilton 圈。输出：在给定的 Hamilton 圈上降低权而获得较优的 Hamilton 圈。 procedure ApproxTSP Begin （1）任意选定一个 Hamiltion 圈，将圈上的顶点顺次记为 1 2 , , , v v v v ，则该圈为 1 2 2 3 1 1 { , , , , } C v v v v v v v v = v v v − （2）while 存在 i≠j 使得( 1 1 , i i j j v v v v C + +  , 1 , ( ) i j i j v v v v E G +  ) do if 1 1 1 1 ( ) ( ) ( ) ( ) w v v w v v w v v w v v i j i j i i j j +  + + + + + then (2.1) 1 1 1 1 ( { , }) { , } C C v v v v v v v v = −  i i j j i j i j + + + + (2.2) 将新的圈 C 上的顶点顺次记为 1 2 , , , v v v v end if end while End /* ApproxTSP */ 1.5.2 TSP 问题的并行算法并行算法实际上是对串行算法的改进，主要是在算法 16.9 的步骤(1)上的改进。每个从进程检查原来的圈上不同的对边，即对进程 k k n (1 )   ，检查下标索引为 i，j 的对边， 1 1 1 1 ( , ) ( , ) ( , ) ( , ) w v v w v v w v v w v v i j i j i i j j +  + + + + + 是否成立；如果成立，则记下减小的权；在每一轮上，选择权减小最多的对边来改进原圈，得到新的改良圈；直到不能有任何改进为止。得到的改进算法仍然是近似算法。算法 16.10 并行 TSP 算法输入：任意不同两点之间的距离 w(i,j)。输出：在这些给定点上的一个较优的回路