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

4组合优化 组合优化问题在实践中有着广泛的应用,同时也是计算机科学中的重要研究课题。本章 对于八皇后问题、SAT问题、装箱问题、背包问题及TSP问题等五个经典的组合优化问题, 给出其定义、串行算法描述、并行算法描述以及并行算法的MPI源程序, 1.1八皇后问题 1.1.1八皇后问题及其串行算法 所谓八皇后问题( Eight Queens Problem),是在8*8格的棋盘上,放置8个皇后。要求 每行每列放一个皇后而且每一条对角线和每一条反对角线上最多只能有一个皇后,即对同 时放置在棋盘的任意两个皇后(1,元)和(2,2),不允许(1-12)=(-12)或者 (+1)=(i2+2)的情况出现 八皇后问题的串行解法为如下的递归算法: 算法16.1八皇后问题的串行递归算法 /*从 chessboard的第row行开始放置皇后* procedure Place Queens( chessboard, row) oIn if row >8 then OutputResult( chessboard) /*结束递归并输出结果* for col=lto8do/*判断是否有列、对角线或反对角线冲突* (1)no collision=true (2)i= (3) while no collision and i< row do (3.1) if collides(i, chessboard[i], row, col)then no collision end if (3.2)i=i+1 end while (4) if no collision then (41) chessboard row]=col/*在当前位置放置一个皇后* /*递归地从下一行开始放置皇后* end for end if End/ Place Queens *

1 1. 4 组合优化 组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题。本章 对于八皇后问题、SAT 问题、装箱问题、背包问题及 TSP 问题等五个经典的组合优化问题， 给出其定义、串行算法描述、并行算法描述以及并行算法的 MPI 源程序。 1.1 八皇后问题 1.1.1 八皇后问题及其串行算法 所谓八皇后问题（Eight Queens Problem），是在 8*8 格的棋盘上，放置 8 个皇后。要求 每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同 时 放 置在 棋盘 的 任意 两个 皇 后 1 1 ( , ) i j 和 2 2 ( , ) i j ， 不 允许 1 2 1 2 ( ) ( ) i i j j − = − 或 者 1 1 2 2 ( ) ( ) i j i j + = + 的情况出现。 八皇后问题的串行解法为如下的递归算法： 算法 16.1 八皇后问题的串行递归算法 /* 从 chessboard 的第 row 行开始放置皇后 */ procedure PlaceQueens(chessboard, row) Begin if row > 8 then OutputResult(chessboard) /* 结束递归并输出结果 */ else for col = 1 to 8 do /* 判断是否有列、对角线或反对角线冲突 */ （1）no_collision = true （2）i = 1 （3）while no_collision and i < row do （3.1）if collides(i, chessboard[i], row, col) then no_collision = false end if （3.2）i = i + 1 end while （4）if no_collision then （4.1）chessboard[row] = col /* 在当前位置放置一个皇后 */ （4.2）go(step + 1, place) /* 递归地从下一行开始放置皇后 */ end if end for end if End /* PlaceQueens */

12八皇后问题的并行算法 该算法是将八皇后所有可能的解置于相应的棋盘上,主进程负责生成初始化的棋盘,并 将该棋盘发送到某个空闲的从进程,由该从进程求出该棋盘上满足初始化条件的所有的解 这里,我们假定主进程只初始化棋盘的前两列,即在棋盘的前两列分别放上2个皇后,这样 就可以产生8*8=64个棋盘 算法162八皇后问题的并行算法 (1)主进程算法 procedure Eight QueensMaster Begin (1) active slaves =n (2) while active slaves >0 do (2.1)从某个从进程i接收信号 signal (2.2) if signal= Accomplished then从从进程i接收并记录解 end if (2.3) if has more boards then (i)向从进程i发送 New Task信号 (ⅱi)向从进程i发送一个新棋盘 (i)向从进程i发送 Terminate信号 ii)active slaves =active slaves-I end while End/* Eight Queens Master * (2)从进程算法 procedure Eight Queen Slave Begin (1)向主进程发送 Ready信号 (2) finished= fal (3) while not finished do (3.1)从主进程接收信号 signal (3.2) if signal = New Task then (i)从主进程接收新棋盘 i)if新棋盘合法then 在新棋盘的基础上找出所有合法的解,并将解发送给主进程 end if else/*signal Terminate */ finished =true end if end while End/* Eight Queen Slave MPI源程序请参见章末附录

2 1.1.2 八皇后问题的并行算法 该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并 将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。 这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上 2 个皇后，这样 就可以产生 8 * 8 = 64 个棋盘。 算法 16.2 八皇后问题的并行算法 （1）主进程算法 procedure EightQueensMaster Begin （1）active_slaves = n （2）while active_slaves > 0 do （2.1）从某个从进程 i 接收信号 signal （2.2）if signal = Accomplished then 从从进程 i 接收并记录解 end if （2.3）if has_more_boards then (ⅰ)向从进程 i 发送 NewTask 信号 (ⅱ)向从进程 i 发送一个新棋盘 else (ⅰ)向从进程 i 发送 Terminate 信号 (ⅱ)active_slaves = active_slaves - 1 end if end while End /* EightQueensMaster */ （2）从进程算法 procedure EightQueenSlave Begin （1）向主进程发送 Ready 信号 （2）finished = false （3）while not finished do （3.1）从主进程接收信号 signal （3.2）if signal = NewTask then (ⅰ)从主进程接收新棋盘 (ⅱ)if 新棋盘合法 then 在新棋盘的基础上找出所有合法的解，并将解发送给主进程 end if else /* signal = Terminate */ finished = true end if end while End /* EightQueenSlave */ MPI 源程序请参见章末附录

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

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

(ii) return true else (i)向所有从进程发送终止信号 (ii) return false (i)向p发送下一个任务 end if end if end while End / PDPMaster * (2)从进程算法 procedure PDPSlave for each processor pi, where I≤i≤kdo while true do (1)从主进程接收信号 (2) if signal= task then (i)用该任务更新F (ⅱ)将DP(F)的结果发送给主进程 else if signal terminal then return end if end if end while nd for End/* PDPSlave * 3算法实现的说明 在这里我们实际上利用了集中控制的动态负载平衡技术,由主进程控制一个任务队列 首先给每个从进程发送一个任务,然后不断从这个队列中取出任务,并通过与相应的进程应 答决定是发送给它新的任务,还是结束所有进程。而从进程不断从主进程中接收信号,决定 是执行新的计算任务还是结束。 众所周知,DP算法中的拆分文字是非常重要的,特别是早期的文字拆分更显得举足轻 重,因为早期的错误会导致多搜索一个子树,工作量几乎增加一倍。例如,Gent和 Walsh 就给出了一个这样的例子,早期的文字选择错误导致了先求解一个具有350000个分枝 的不可满足的子问题。如果在初始的文字拆分中,提高DP算法的拆分文字的命中率,无疑 会达到事半功倍的效果 为了提高拆分文字的命中率,编程实现中,主进程划分任务的时候,预先找出CNF范 式中的纯文字和单元子句,这样就大大减少了需要搜索的子树数 MPⅠ源程序请参见所附光盘

5 （ii）return true else if (j > 2n ) then （i）向所有从进程发送终止信号 （ii）return false else （i）向 pi 发送下一个任务 end if end if end while End /* PDPMaster */ （2）从进程算法 procedure PDPSlave Begin for each processor pi，where 1 i k do while true do （1）从主进程接收信号 （2）if signal = task then （i）用该任务更新 F （ii）将 DP(F)的结果发送给主进程 else if signal = terminal then return end if end if end while end for End /* PDPSlave */ 3.算法实现的说明 在这里我们实际上利用了集中控制的动态负载平衡技术，由主进程控制一个任务队列。 首先给每个从进程发送一个任务，然后不断从这个队列中取出任务，并通过与相应的进程应 答决定是发送给它新的任务，还是结束所有进程。而从进程不断从主进程中接收信号，决定 是执行新的计算任务还是结束。 众所周知，DP 算法中的拆分文字是非常重要的，特别是早期的文字拆分更显得举足轻 重，因为早期的错误会导致多搜索一个子树，工作量几乎增加一倍。例如，Gent 和 Walsh 就给出了一个这样的例子，早期的文字选择错误导致了先求解一个具有 350,000,000 个分枝 的不可满足的子问题。如果在初始的文字拆分中，提高 DP 算法的拆分文字的命中率，无疑 会达到事半功倍的效果。 为了提高拆分文字的命中率，编程实现中，主进程划分任务的时候，预先找出 CNF 范 式中的纯文字和单元子句，这样就大大减少了需要搜索的子树数目。 MPI 源程序请参见所附光盘