并行計算-實驗指導(dǎo)-實驗04組合優(yōu)化

實驗4組合優(yōu)化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.小結(jié)

157.參考文獻(xiàn)

168.附錄八皇后問題并行算法的MPI源程序

16組合優(yōu)化問題在實踐中有著廣泛的應(yīng)用，同時也是計算機(jī)科學(xué)中的重要研究課題。本章對于八皇后問題、SAT問題、裝箱問題、背包問題及TSP問題等五個經(jīng)典的組合優(yōu)化問題，給出其定義、串行算法描述、并行算法描述以及并行算法的MPI源程序。1八皇后問題1.1八皇后問題及其串行算法所謂八皇后問題（EightQueensProblem），是在8*8格的棋盤上，放置8個皇后。要求每行每列放一個皇后,而且每一條對角線和每一條反對角線上最多只能有一個皇后，即對同時放置在棋盤的任意兩個皇后和，不允許或者的情況出現(xiàn)。八皇后問題的串行解法為如下的遞歸算法：算法16.1八皇后問題的串行遞歸算法/*從chessboard的第row行開始放置皇后*/procedurePlaceQueens(chessboard,row)Beginifrow>8thenOutputResult(chessboard)

/*結(jié)束遞歸并輸出結(jié)果*/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

/*在當(dāng)前位置放置一個皇后*/（4.2）go(step+1,place)

/*遞歸地從下一行開始放置皇后*/endifendforendifEnd/*PlaceQueens*/1.2八皇后問題的并行算法該算法是將八皇后所有可能的解置于相應(yīng)的棋盤上，主進(jìn)程負(fù)責(zé)生成初始化的棋盤，并將該棋盤發(fā)送到某個空閑的從進(jìn)程，由該從進(jìn)程求出該棋盤上滿足初始化條件的所有的解。這里，我們假定主進(jìn)程只初始化棋盤的前兩列，即在棋盤的前兩列分別放上2個皇后，這樣就可以產(chǎn)生8*8=64個棋盤。算法16.2八皇后問題的并行算法（1）主進(jìn)程算法procedureEightQueensMasterBegin（1）active_slaves=n（2）whileactive_slaves>0do（2.1）從某個從進(jìn)程i接收信號signal（2.2）ifsignal=Accomplishedthen從從進(jìn)程i接收并記錄解endif（2.3）ifhas_more_boardsthen(ⅰ)向從進(jìn)程i發(fā)送NewTask信號(ⅱ)向從進(jìn)程i發(fā)送一個新棋盤else(ⅰ)向從進(jìn)程i發(fā)送TermiNATe信號(ⅱ)active_slaves=active_slaves-1endifendwhileEnd/*EightQueensMaster*/（2）從進(jìn)程算法procedureEightQueenSlaveBegin（1）向主進(jìn)程發(fā)送Ready信號（2）finished=false（3）whilenotfinisheddo（3.1）從主進(jìn)程接收信號signal（3.2）ifsignal=NewTaskthen(ⅰ)從主進(jìn)程接收新棋盤(ⅱ)if新棋盤合法then在新棋盤的基礎(chǔ)上找出所有合法的解，并將解發(fā)送給主進(jìn)程endifelse/*signal=TermiNATe*/finished=trueendifendwhileEnd/*EightQueenSlave*/MPI源程序請參見章末附錄。2SAT問題2.1SAT問題及其串行算法1.SAT問題描述所謂可滿足性問題（SatisfiabilityProblem）即SAT問題，其定義為：對于一個命題邏輯公式，是否存在對其變元的一個真值賦值公式使之成立。這個問題在許多領(lǐng)域都有著非常重要的意義，而且對其快速求解算法的研究成為計算機(jī)科學(xué)的核心課題之一。例如在機(jī)器定理證明領(lǐng)域，某命題是否是一個相容的公理集合的推論，這個問題歸結(jié)為該命題的反命題與該公理集合一起是否是不可滿足的。特別是1971年Cook首次證明了SAT是NP-完全的，從而大量的計算問題都可以歸結(jié)到SAT。正是由于SAT重要的理論和應(yīng)用地位，眾多學(xué)者對它進(jìn)行了廣泛而深入的研究。由命題邏輯知識可以知道，任何命題邏輯公式都邏輯等價與一個合取范式(Conjunctive

NormalForm，簡寫為CNF),因此本文只討論CNF的SAT求解問題。下面給出幾種常見的SAT問題化簡策略，以下均假定F是CNF范式：①單元子句規(guī)則：若C=｛L｝是F的子句，則F變?yōu)镕’=F[F/1]；②純文字規(guī)則：若文字L出現(xiàn)在F中，而L不出現(xiàn)F中，則L稱為F的純文字。F變?yōu)镕’=F[F/1]；③重言子句規(guī)則：若C∈F且C是重言子句，則從F中刪去C得F’=F-C；④兩次出現(xiàn)規(guī)則：若L∈C1，L∈C2，且L和L都不在其它子句中出現(xiàn)，則將C1，C2合并為C’=(C1-｛L｝)∪(C2-｛L｝)，F(xiàn)變?yōu)镕’=F-｛C1,C2｝∪｛C’｝；⑤包含規(guī)則：若C1，C2是F的子句，且C1∈C2，則F中刪去C2，得F’=F-｛C2｝。2.SAT問題串行算法SAT問題的DP算法是由M.Davis和H.Putnam于1960年首次提出[2]，現(xiàn)在已經(jīng)成為最著名的SAT算法，其描述如下：算法16.3SAT問題的DP算法輸入：合取范式F。輸出：F是否可滿足。procedureDP(F)Begin(1)

ifF為空公式thenreturnYesendif(2)

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

ifF包含一個子句{l}then

/*單元子句規(guī)則*/returnDP(F[l/1])endif

(4)

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

/*純文字規(guī)則*/returnDP(F[l/1])endif(5)

選擇一個未賦值的文字l(6)

/*拆分*/ifDP(F[l/1])=YesthenreturnYeselsereturnDP(F[l/0])endifEnd/*DP*/可以看出，DP算法是對回溯算法的精化，其中應(yīng)用了我們在前面提到的化簡策略單元子句規(guī)則和純文字規(guī)則。前面已經(jīng)介紹過，這些策略并不能在數(shù)量級上降低算法的時間復(fù)雜度，但實驗證明這些策略的應(yīng)用可以極大的改善平均性能。其實，上面介紹的策略都可以應(yīng)用于SAT的求解，而且已經(jīng)有了這方面的工作。2.2SAT問題的并行算法1.并行化思路通過我們在前面對串行DP算法的介紹可以看出，實際上DP算法仍然是利用深度優(yōu)先方法對可能的解空間做深度優(yōu)先搜索，這樣我們?nèi)匀豢梢园堰@個解空間看成一棵二叉樹。而它與回溯搜索算法的區(qū)別僅僅在于它利用了SAT的一些性質(zhì)巧妙的找到了一些僅有一種賦值可能的文字，這樣就有效地減少了搜索開銷。同時在搜索一棵子樹時，對某個文字的賦值可能導(dǎo)致新的單元子句的產(chǎn)生，這樣，從平均意義上考慮，對這一性質(zhì)的反復(fù)利用可以極大地加快搜索速度。容易知道，對于尋找單元子句和純文字的工作是在多項式時間內(nèi)完成的，因此我們可以由主進(jìn)程預(yù)先把CNF的所有單元子句和純文字找出來，對它們分別賦上可能使CNF得到滿足的值，并按照某種策略選取n個文字對他們預(yù)先賦值，共得到2n組解。然后把這些信息分別發(fā)送給各個從進(jìn)程進(jìn)行計算，并收集運(yùn)算結(jié)果。這樣既避免了各個從進(jìn)程重復(fù)尋找單元子句和純文字，又有可能通過對選出的n個文字的賦值產(chǎn)生了新的單元子句，從而加快了整個程序的搜索速度。2.并行DP算法算法16.4SAT問題的并行DP算法輸入：合取范式F。輸出：F是否可滿足。（1）主進(jìn)程算法procedurePDPMaster(F)Begin（1）找出n個文字，并初始化任務(wù)隊列（2）j=0（3）向每個從進(jìn)程發(fā)送一個任務(wù)（4）whiletrue

do（4.1）某個從進(jìn)程pi接收結(jié)果（4.2）ifresult=truethen（i）向所有從進(jìn)程發(fā)送終止信號（ii）returntrueelseif(j>2n)then（i）向所有從進(jìn)程發(fā)送終止信號（ii）returnfalseelse（i）向pi發(fā)送下一個任務(wù)endifendifendwhileEnd/*PDPMaster*/（2）從進(jìn)程算法procedurePDPSlaveBeginforeachprocessorpi，wheredowhiletruedo（1）從主進(jìn)程接收信號（2）ifsignal=taskthen（i）用該任務(wù)更新F（ii）將DP(F)的結(jié)果發(fā)送給主進(jìn)程elseifsignal=terminalthenreturnendifendifendwhileendforEnd/*PDPSlave*/3.算法實現(xiàn)的說明在這里我們實際上利用了集中控制的動態(tài)負(fù)載平衡技術(shù)，由主進(jìn)程控制一個任務(wù)隊列。首先給每個從進(jìn)程發(fā)送一個任務(wù)，然后不斷從這個隊列中取出任務(wù)，并通過與相應(yīng)的進(jìn)程應(yīng)答決定是發(fā)送給它新的