并行计算-实验指导-实验04组合优化

实验4组合优化1.1八皇后问题

11.1八皇后问题及其串行算法

11.2八皇后问题的并行算法

22.2SAT问题

42.1SAT问题及其串行算法

42.2SAT问题的并行算法

53.3装箱问题

73.1装箱问题及其串行算法

73.2装箱问题的并行算法

84.4背包问题

104.1背包问题及其串行算法

104.2背包问题的并行算法

125.4TSP问题

125.1TSP问题及其串行算法

125.2TSP问题的并行算法

136.小结

157.参考文献

168.附录八皇后问题并行算法的MPI源程序

16组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题。本章对于八皇后问题、SAT问题、装箱问题、背包问题及TSP问题等五个经典的组合优化问题，给出其定义、串行算法描述、并行算法描述以及并行算法的MPI源程序。1八皇后问题1.1八皇后问题及其串行算法所谓八皇后问题（EightQueensProblem），是在8*8格的棋盘上，放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同时放置在棋盘的任意两个皇后和，不允许或者的情况出现。八皇后问题的串行解法为如下的递归算法：算法16.1八皇后问题的串行递归算法/*从chessboard的第row行开始放置皇后*/procedurePlaceQueens(chessboard,row)Beginifrow>8thenOutputResult(chessboard)

/*结束递归并输出结果*/elseforcol=1to8do

/*判断是否有列、对角线或反对角线冲突*/（1）no_collision=true（2）i=1（3）whileno_collisionandi<rowdo（3.1）ifcollides(i,chessboard[i],row,col)thenno_collision=falseendif（3.2）i=i+1endwhile（4）ifno_collisionthen（4.1）chessboard[row]=col

/*在当前位置放置一个皇后*/（4.2）go(step+1,place)

/*递归地从下一行开始放置皇后*/endifendforendifEnd/*PlaceQueens*/1.2八皇后问题的并行算法该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上2个皇后，这样就可以产生8*8=64个棋盘。算法16.2八皇后问题的并行算法（1）主进程算法procedureEightQueensMasterBegin（1）active_slaves=n（2）whileactive_slaves>0do（2.1）从某个从进程i接收信号signal（2.2）ifsignal=Accomplishedthen从从进程i接收并记录解endif（2.3）ifhas_more_boardsthen(ⅰ)向从进程i发送NewTask信号(ⅱ)向从进程i发送一个新棋盘else(ⅰ)向从进程i发送TermiNATe信号(ⅱ)active_slaves=active_slaves-1endifendwhileEnd/*EightQueensMaster*/（2）从进程算法procedureEightQueenSlaveBegin（1）向主进程发送Ready信号（2）finished=false（3）whilenotfinisheddo（3.1）从主进程接收信号signal（3.2）ifsignal=NewTaskthen(ⅰ)从主进程接收新棋盘(ⅱ)if新棋盘合法then在新棋盘的基础上找出所有合法的解，并将解发送给主进程endifelse/*signal=TermiNATe*/finished=trueendifendwhileEnd/*EightQueenSlave*/MPI源程序请参见章末附录。2SAT问题2.1SAT问题及其串行算法1.SAT问题描述所谓可满足性问题（SatisfiabilityProblem）即SAT问题，其定义为：对于一个命题逻辑公式，是否存在对其变元的一个真值赋值公式使之成立。这个问题在许多领域都有着非常重要的意义，而且对其快速求解算法的研究成为计算机科学的核心课题之一。例如在机器定理证明领域，某命题是否是一个相容的公理集合的推论，这个问题归结为该命题的反命题与该公理集合一起是否是不可满足的。特别是1971年Cook首次证明了SAT是NP-完全的，从而大量的计算问题都可以归结到SAT。正是由于SAT重要的理论和应用地位，众多学者对它进行了广泛而深入的研究。由命题逻辑知识可以知道，任何命题逻辑公式都逻辑等价与一个合取范式(Conjunctive

NormalForm，简写为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.3SAT问题的DP算法输入：合取范式F。输出：F是否可满足。procedureDP(F)Begin(1)

ifF为空公式thenreturnYesendif(2)

ifF包含一个空子句thenreturnNoendif(3)

ifF包含一个子句{l}then

/*单元子句规则*/returnDP(F[l/1])endif

(4)

ifF包含一个文字l，但不包含lthen

/*纯文字规则*/returnDP(F[l/1])endif(5)

选择一个未赋值的文字l(6)

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

do（4.1）某个从进程pi接收结果（4.2）ifresult=truethen（i）向所有从进程发送终止信号（ii）returntrueelseif(j>2n)then（i）向所有从进程发送终止信号（ii）returnfalseelse（i）向pi发送下一个任务endifendifendwhileEnd/*PDPMaster*/（2）从进程算法procedurePDPSlaveBeginforeachprocessorpi，wheredowhiletruedo（1）从主进程接收信号（2）ifsignal=taskthen（i）用该任务更新F（ii）将DP(F)的结果发送给主进程elseifsignal=terminalthenreturnendifendifendwhileendforEnd/*PDPSlave*/3.算法实现的说明在这里我们实际上利用了集中控制的动态负载平衡技术，由主进程控制一个任务队列。首先给每个从进程发送一个任务，然后不断从这个队列中取出任务，并通过与相应的进程应答决定是发送给它新的