《論文_并行計(jì)算-實(shí)驗(yàn)指導(dǎo)-實(shí)驗(yàn)04組合優(yōu)化(定稿)》

1、實(shí)驗(yàn)4組合優(yōu)化1八皇后問題11.1八皇后問題及其串行算法11.2八皇后問題的并行算法22 sat問題42. 1 sat問題及其串行算法42. 2 sat問題的并行算法53裝箱問題73. 1裝箱問題及其串行算法73.2裝箱問題的并行算法84背包問題104. 1背包問題及其串行算法1042背包問題的并行算法124 tsp 問題125.1 tsp問題及其串行算法125. 2 tsp問題的并行算法13小結(jié)15參考文獻(xiàn)16附錄八皇后問題并行算法的mpi源程序16組合優(yōu)化問題呑實(shí)踐中有著廣泛的應(yīng)用,同時(shí)也是計(jì)算機(jī)科學(xué)中的重要研究課題。本章對于八皇后問題、sat問題、裝箱問題、背包問題及tsp問題等五個(gè)經(jīng)典

2、的組合優(yōu)化問題,給出其定義、串行算法描述、 并行算法描述以及并行算法的mpi源程序。1八皇后問題1.1八皇后問題及其串行算法所謂八皇后問題(eight queens problem),是在8*8格的棋盤上,放賈8個(gè)皇后。要求每行每列放- 個(gè)皇后,而且每一條對角線和每一條反對角線上最多只能有一個(gè)皇后,即對同時(shí)放置在棋盤的任意兩個(gè)皇 后a，j)和,不允許或者j) = (i2十j?)的情況出現(xiàn)。八皇后問題的串行解法為如下的遞歸算法:算法16. 1八皇后問題的串行遞歸算法/*從chessboard的第tow行開始放置皇后*/procedure placequeens (chessboard, row)

3、beginif row > 8 thenoutputresul t (chessboard)/* 結(jié)束遞歸并輸出結(jié)果 */elsefor col = 1 to 8 do /*判斷是否有列、對角線或反對角線沖突*/(1) no_collision = true(2) i = 1(3) while nocolli si on and i < row do(3. 1) if col 1 ides (i, chessboardi, row, col) thenno_col 1 is ion = falseend if(3. 2) i 二 i + 1 end while(4) if no c

4、ollision then(4. 1) chessboard row = col /*在當(dāng)前位置放置一個(gè)皇后*/(4. 2) go (step + lt place) /*遞歸地從下一行開始放置皇后*/end ifend forend ifend /* placequeens */1. 2八皇后問題的并行算法該算法是將八皇后所有可能的解置于相應(yīng)的棋盤上,主進(jìn)程負(fù)責(zé)生成初始化的棋盤，并將該棋盤發(fā)送 到某個(gè)空閑的從進(jìn)程,山該從進(jìn)程求出該棋盤上滿足初始化條件的所有的解。這里,我們假定主進(jìn)程只初 始化棋盤的前兩列,即在棋盤的前兩列分別放上2個(gè)皇后,這樣就可以產(chǎn)生8 * 8 = 64個(gè)棋盤.算法16.

5、2八皇后問題的并行算法(1) 主進(jìn)程算法procedure eigh tquecnsmas terbegin(1) act!ve slaves = n(2) while active slaves > 0 do(2. 1)從某個(gè)從進(jìn)程i接收信號signal(2. 2) if signal = accomplished then 從從進(jìn)程 i 接收并記錄解end if(2. 3) if has_more_ boards then(i )向從進(jìn)程i發(fā)送newtask信號(ii)向從進(jìn)程i發(fā)送一個(gè)新棋盤else(i )向從進(jìn)程i發(fā)送terminate信號(ii)active_slaves =

6、active_slaves - 1end ifend whi leend /* eigh tqueensmas ter */(2) 從進(jìn)程算法procedure eigh tqueensla vebegin(1) 向主進(jìn)程發(fā)送ready信號(2) finished = false(3) while not finished do(3. 1)從主進(jìn)程接收信號signal(3. 2) if signal = newtask then(i )從主進(jìn)程接收新棋盤(ii)if新棋盤合法then在新棋盤的基礎(chǔ)上找出所有合法的解，并將解發(fā)送給主進(jìn)程end ifelse /* signal = tormina

7、 te */finished = trueend ifend whileend /* ei gh t queens i a ve */mp1源程序請參見章末附錄。2 sat問題2. 1 sat問題及其串行算法1. sat問題描述所謂可滿足性問題(satisfiability problem)即sat問題,其定義為:對丁一個(gè)命題邏輯公式,是 否存在對其變元的一個(gè)真值賦值公式使z成立。這個(gè)問題在許多領(lǐng)域都有著非常重要的意義,而h對其快 速求解算法的研究成為計(jì)算機(jī)科學(xué)的核心課題之一。例如在機(jī)器定理證明領(lǐng)域,某命題是否是一個(gè)相容的 公理集合的推論,這個(gè)問題歸結(jié)為該命題的反命題與該公理集合一起是否是不對

8、滿足的。特別是1971年 cook首次證明了 sat是np-完全的,從而大量的計(jì)算問題都町以歸結(jié)到sat。止是山于sat重要的理論和 應(yīng)用地位,眾多學(xué)者對它進(jìn)行了廣泛而深入的研究。山命題邏輯知識(shí)可以知道,任何命題邏輯公式都邏輯等價(jià)與一個(gè)合取范式(conjunctive normal form,簡寫為cnf),因此本文只討論cnf的sa t求解問題。下面給出幾種常見的sat問題化簡策略,以下均假定f是cnf范式:單元子句規(guī)則:若o l是 f的子句,則f變?yōu)閒，ff/1；純文字規(guī)則:若文字l出現(xiàn)在f中,而f.不出現(xiàn)f中,則l稱為f 的純文字。f變?yōu)閒，=ff/1j；重言子句規(guī)則:若cwf且c是重言

9、子句,則從f中刪去c得f，=fc； 兩次出現(xiàn)規(guī)則:若iq, rlwc?,且l和rl都不在其它子句中出現(xiàn),則將g , c2合并為c，=( c- l )u( c2- ul), f 變?yōu)?f，=f- (c, cj u (cf ；包含規(guī)則:若 ci ,匕是 f 的子句，h. g cc2,則f 中刪去 g,得f，=f c2o2. sat問題串行算法sa t問題的dp算法是由m. da vis和il pu tnam t i960年首次捉岀,現(xiàn)在己經(jīng)成為最著名的sat算法,其描述如下:算法16. 3 sat問題的dp算法輸入:合取范式f。輸出:f是否可滿足。procedure dp(f)begin(1) i

10、f f為空公式thenreturn yesend if(2) if f包含一個(gè)空子句thenre turn noend if(3) if f包含一個(gè)子句1 then/*單元子句規(guī)則*/re turn dp (f1/1)end if(4) if f包含-個(gè)文字1,但不包含rl then /*純文字規(guī)則*/re turn dp (f1/1)end if(5) 選擇一個(gè)未賦值的文字1(6) /* 拆分 */if dp(f 1/1j) - yes thenreturn yeselsere turn dp(f 1/0)end ifend /* dp */可以看出,d卩算法是對冋溯算法的精化,其中應(yīng)用了我

11、們在前而提到的化簡策略單元子句規(guī)則和純文 字規(guī)則。前面已經(jīng)介紹過,這些策略并不能在數(shù)量級上降低算法的時(shí)間復(fù)雜度,但實(shí)驗(yàn)證明這些策略的應(yīng) 用可以極大的改善平均性能。其實(shí)，上而介紹的策略都可以應(yīng)用于sat的求解,而冃己經(jīng)有了這方而的工 作。2. 2 sat問題的并行算法1.并行化思路通過我們在前面對串行dp算法的介紹可以看出,實(shí)際.上dp算法仍然是利川深度優(yōu)先方法對可能的解 空間做深度優(yōu)先搜索,這樣我們?nèi)匀豢梢园堰@個(gè)解空間看成一棵二叉樹。而它與回溯搜索算法的區(qū)別僅僅 在于它利用了 sat的一些性質(zhì)巧妙的找到了一些僅有種賦值可能的文字,這樣就有效地減少了搜索開銷。 同時(shí)在搜索一棵子樹時(shí),對某個(gè)文字的

12、賦值可能導(dǎo)致新的單元子句的產(chǎn)牛,這樣,從平均意義上考慮,對 這一性質(zhì)的反復(fù)利用可以極大地加快搜索速度。容易知道,對于尋找單元子句和純文字的工作是奮多項(xiàng)式 吋間內(nèi)完成的,因此我們可以由主進(jìn)程預(yù)先把cnf的所有單元子句和純文字找出來,對它們分別賦上可能 使cnf得到滿足的值,并按照某種策略選取n個(gè)文字對他們預(yù)先賦值,共得到2組解。然后把這些信息分 別發(fā)送給各個(gè)從進(jìn)程進(jìn)行計(jì)算，并收集運(yùn)算結(jié)果。這樣既避免了各個(gè)從進(jìn)程重復(fù)尋找單元子旬和純文字, 又有對能通過對選出的n個(gè)文字的賦值產(chǎn)牛了新的單元子句,從而加快了整個(gè)程序的搜索速度。2并行dp算法算法16. 4 sat問題的并行dp算法輸入:合取范式f。輸出

13、:f是否可滿足。（1）主進(jìn)程算法procedure pdpmaster (f)begin(1) 找出n個(gè)文字,并初始化任務(wù)隊(duì)列(2) j = 0(3) 向每個(gè)從進(jìn)程發(fā)送一個(gè)任務(wù)(4) while true do(4. 1)某個(gè)從進(jìn)稈p,接收結(jié)果(4. 2) if result = true then(i) 向所有從進(jìn)程發(fā)送終止信號(ii) return trueelseif (j > 2) then(i) 向所有從進(jìn)程發(fā)送終止信號(ii) return falseelse(i)向pi發(fā)送卜一個(gè)任務(wù)end ifend ifend whileend /* pdpmaster */(2)從進(jìn)程

14、算法procedure pdpslavebeginfor each processor p” where 1< i < k dowhile true do(1) 從主進(jìn)程接收信號(2) if signal = task then(i) 用該任務(wù)更新f(ii) 將dp(f)的結(jié)果發(fā)送給主進(jìn)程else if signal = terminal thenreturnend ifend ifend whileend forend /* pdfs lave */3. 算法實(shí)現(xiàn)的說明在這里我們實(shí)際上利用了集中控制的動(dòng)態(tài)負(fù)載平衡技術(shù),山主進(jìn)程控制一個(gè)任務(wù)隊(duì)列。首先給每個(gè)從 進(jìn)程發(fā)送一個(gè)任務(wù),然后

15、不斷從這個(gè)隊(duì)列中取出任務(wù),并通過與相應(yīng)的進(jìn)程應(yīng)答決定是發(fā)送給它新的任務(wù), 還是結(jié)束所有進(jìn)程。而從進(jìn)程不斷從主進(jìn)程中接收信號,決定是執(zhí)疔新的計(jì)算任務(wù)還是結(jié)朿。眾所周知,dp算法中的拆分文字是非常重要的,特別是早期的文字拆分更顯得舉足輕重,因?yàn)樵缙诘?錯(cuò)誤會(huì)導(dǎo)致多搜索一個(gè)子樹,工作量兒乎增加一倍。例如,gont和walsh就給出了一個(gè)這樣的例子,早期 的文字選擇錯(cuò)誤導(dǎo)致了先求解一個(gè)具有350, 000, 000個(gè)分枝的不對滿足的子問題。如果在初始的文字拆分 中,提高dp算法的拆分文字的命中率，無疑會(huì)達(dá)到事半功倍的效果。為了提高拆分文字的命小率,編程實(shí)現(xiàn)屮,主進(jìn)程劃分任務(wù)的時(shí)候,預(yù)先找出cnf范式中

16、的純文字和 單元子句,這樣就大大減少了需要搜索的子樹數(shù)目。mpi源程序請參見所附光盤。3裝箱問題3. 1裝箱問題及其吊行算法經(jīng)典的一維裝箱問題(bin packing problem)是指,給定%件物品的序列只宀，“，物品 勺(1 <i<n)的大小g e (0,1,要求將這些物品裝入單位容量7的箱子&屁,心中,使得每個(gè)箱 子中的物品大小之和不超過1,并使所使用的箱子數(shù)目皿最小。下次適應(yīng)算法(next fit algorithm)是最早提出的、最簡單的一個(gè)在線算法,joh73首次仔細(xì)分 析了下次適應(yīng)算法的最壞情況性能。下次適應(yīng)算法維持一個(gè)當(dāng)前打開的箱子,它依序處理輸入物胡,當(dāng)

17、物 品到達(dá)時(shí)檢查該物品能否放入這個(gè)當(dāng)前打開的箱子中,若能則放入;否則把物品放入一個(gè)新的箱子中，并 把這個(gè)新箱子作為當(dāng)前打開的箱子。算法描述如下:算法16. 5裝箱問題的下次適應(yīng)算法輸入:輸入物品序列l(wèi) =< °心,、a“ >。輸出:使用的箱子數(shù)各裝入物品的箱子p =< b,b“ 芒小>。procedure nextfitbegin(1) s(b) = 1/*初始化當(dāng)前打開的箱子b,令b已滿*/(2) m = 0/*使用箱子計(jì)數(shù)*/(3) for i = 1 to n doif s (a.) + s (b) £ 1 then(i) s(b)二 s(b)

18、 +/* 把&放入 13中 */else/*使川的箱子數(shù)加一 */*新打開箱子氐*/*把&放入b中*/(i) m = m + 1(ii) b = &(hi) s(b) = s(a,) end ifend forend /* next fit */32裝箱問題的并行算法算法16. 5使用一遍掃描物品序列來實(shí)現(xiàn),本身具有固有的順序性,其時(shí)間復(fù)朵度為0(n)。我們使用 平衡樹和倍增技術(shù)對其進(jìn)行并行化。首先利川前綴和算法建立一個(gè)鏈表簇，令ai為輸入物品序列中第i 件物品的大小,如果鏈表指針山aj指向ak,則表示aj+aj+l+ak>l且 aj+aj+1+as 其后利用倍增

19、技術(shù)計(jì)算以al為頭的鏈農(nóng)的長度,而以a(l)為頭的鏈表的長 度即是下次適應(yīng)算法所使川的箱子數(shù)h。接下來利用在上一步驟中產(chǎn)牛的中間數(shù)據(jù)反向建立一棵二叉樹, 使該二叉樹的葉節(jié)點(diǎn)恰好是下次適應(yīng)算法在各箱子中放入的笫一個(gè)物品的序號;最后,根據(jù)各箱子中放入 的第一個(gè)物品的序號,使用二分法確定各物品所放入的箱子的序號。算法16. 6并行下次適應(yīng)算法輸入：數(shù)組al,n,其中ai為輸入物品序列屮第i個(gè)物品的人小。 輸出:使川的箱子數(shù)仃m,每個(gè)物品應(yīng)放入的箱子序號數(shù)組bl,門。 procedure pnextfitbegin(1) 調(diào)用求前綴和的并行算法計(jì)算fj二al+a+aj(2) for j = 1 to

20、n pardo借助fj,使川二分法計(jì)算c0, j= maxkiaj+aj+l+ak <1end for/*以下(3) - (8),計(jì)算下次適應(yīng)算法使用的箱子數(shù)目ni */(3) c0, n+1 = n(4) h = 0(5) for j=l to n pardo e0, j=l end for(6) while ch, 1 # n do(6. 1) h 二 h 十 1(6. 2) for j = 1 to n pardoif ch - 1, j = n then(i) eh, j = eh-lf j(ii) ch, j = ch - 1, jelse(i) eh, j = eh - 1

21、j + eh - l,ch - lf j + 1(ii) ch, j = ch - l,ch - lf j + 1end ifend forend while(7) height = h(8) m = eheigh t, 1(9) /*計(jì)算i)0, j二第j個(gè)箱子中第一件物品在輸入序列中的編號*/for h = height down to 0 dofor j = 1 to n / pardo(i) if j = even then dh, j = ch, dht, j/2+l end if(ii) if j = 1 then dh, 1 = 1 end if(hi) if j = odd &

22、gt; 1 then dh, j = dh-1, j+l/2 endif end for end for(10) for j二1 to n pardo /*計(jì)算bj=第j個(gè)物品所放入的箱子序號*/使用二分法計(jì)算bj = max k / d0, k <j , dof k+1 >j 或者k = m end forend /* pnextfi t */mpt源程序請參見所附光盤。4背包問題4. 1背包問題及其吊行算法01背包問題(ot knapsack problem)的定義為:設(shè)集合a -代表m件物品,止整數(shù)pi, vvr分別表示笫i件物品的價(jià)值與重量,那么0-1背包問題knap(a,

23、 c)定義為,求a的子集,使得重量z和小于 背包的容量c,并使得價(jià)值和最大。也就是說求:mmax 工 p“/=, (16. 1)subject to 工 wixj < c»=ig0,1o解決ot背包問題的最簡單的方法是動(dòng)態(tài)規(guī)劃(dynamic programming)算法。我們先看看knap(a, c)的一個(gè)子問題knap(a)、y ),真vmjrqs，。顯然,若j并不在最優(yōu)解中,那么 knaplazy)的解就是knap0j、y的解。否則,心曲卜,$-)就是knap(ay)的解。設(shè)爪)是 knap(小的最優(yōu)解,我們得到下而的最優(yōu)方法:加)屮1-00 if y<0z/b)

24、= max/j_(y), /(y-wj +/?. (16.2)for all 0 < y < c and 1 < j < m絞片.(c) = (力(0),力，,/«)0 < j < m ,那么,動(dòng)態(tài)規(guī)劃算法就是依次地計(jì)算f, (c),戸2 (c),fin (c)來求解問題。其中fj (c)是knap (aj , c)的最大價(jià)值向量。動(dòng)態(tài)規(guī)劃算法是基于bellon遞歸循環(huán),它是求解決背包問題的最直接的方法?；?16.2)式我們可 以寫出串行算法如下:算法16. 7 0-1背包問題的串行動(dòng)態(tài)規(guī)劃算法輸入：各件物品的價(jià)值i兒,pw各件物品的重量門，背包

25、的容量c°輸出:能夠放入背包的物品的最大總價(jià)值化(c) °procedure knapsack (p, w, c)begin(1) for i = 0 to c do fo (i) = 0 end for(2) for i = 1 to m do(2. 1) fi(0) = 0(2. 2) for j = 1 to c doif 衍 < j thenif pi + fi-i (j - wj > fi-i (j) thenfi (j) = p： + fi-i (j - wi)else fi(j) = fi-i (j) end if else fi (j) = fi

26、-! (j) end ifend for end forend /* knapsack */可以看出,串行的動(dòng)態(tài)規(guī)劃算法需耍占用很大的空間,其木質(zhì)是bellman遞歸,最壞和最好的情況下 的時(shí)間差不多相同。雖然,它在問題規(guī)模比較小時(shí)，可以很好的解決問題,但是,隨著問題規(guī)模的擴(kuò)人, 串行動(dòng)態(tài)規(guī)劃算法就顯得力不從心了。4. 2背包問題的并行算法現(xiàn)在,我們耍做的是把串行程序改成并行程序。首先,我們分析一下串行程序的特點(diǎn)。注意到第(2. 2) 步的for循環(huán),fi(j)只用到上一步fmy)的值,而與同一個(gè)i循環(huán)無關(guān),這樣,可以把第(2.2)步直接并 行化。得到下而的并行算法:算法16. 8 0-1背包

27、問題的并行算法輸入：各件物品的價(jià)值p：p，,各件物品的車量門，背包的容量c°輸出:能夠放入背包的物品的最人總價(jià)值人(c) ° procedure parallelknapsack (p, w, c)begin(1) for each processor 0< j <c do 九(j) = 0 end for(2) for 1=1 to m pardo(2. 1) for each processor 0 < j < doz( j) = /_!(»end for(2. 2) for each processor < j <c do

28、end forend forend /* parallelknapsack */mpt源程序請參見所附光盤。4 tsp問題5.1 tsp問題及其串行算法tsp問題(traveling-salesman problem)討描述為：貨郎到各村去賣貨,再回到出發(fā)處,每村都耍 經(jīng)過h僅經(jīng)過一次,為其設(shè)計(jì)一種路線,使得所用旅行售貨的時(shí)問最短。tsp問題至今還沒有有效的算法,是當(dāng)今圖論上的一大難題。前只能給出近似算法,其中z是所 謂“改良圈算法”,即已知連2jj是g的hamilton圈,用下血的算法把它的權(quán)減小: 算法16.9 tsp問題的改良圈算法 輸入:任意的個(gè)hamilion圈。輸出:在給圧的ham

29、ilion is.卜.降低權(quán)而獲得較優(yōu)的hami 1 ton圈。procedure approxtspbegin(1) 任意選定hami it ion圈,將圈上的頂點(diǎn)順次記為比,“畀,則該圈為c = 時(shí)2，勺3，vr-1兒，人m (2) while 存在 ihj 使得(v,v,-+1, vjvj+l e c , v,.vy, v.vy+1 e £(g) doif w(vzv.) + vv(v.+1v/+1) < w(v.v/+1) + w(vyv.+1) then(21)c = (c-氣m+ivy+i)u v,. vj, v/+l vy+1 end ifend whileend

30、 /* approxtsp */5. 2 tsp問題的并行算法并行算法實(shí)際上是對串行算法的改進(jìn),主要是在算法16.9的步驟(1)上的改進(jìn)。每個(gè)從進(jìn)程檢查原來 的圈上不同的對邊，即對進(jìn)程kq5k5n),檢查下標(biāo)索引為i , j的對邊， w(匕，匕)+吵(片+1，匕+1)v w(匕，匕+) +w(v/，片+)逢冷成広如柴成立；則記下減小的權(quán);在每一輪上,選 擇權(quán)減小最多的對邊來改進(jìn)原圈,得到新的改良圈;直到不能冇任何改進(jìn)為止。得到的改進(jìn)算法仍然是近 似算法。算法16. 10并彳亍tsp算法輸入:任意不同兩點(diǎn)z間的距離w(i, j)。輸出:在這些給定點(diǎn)一上的-個(gè)較優(yōu)的冋路。(1) 主進(jìn)程算法proc

31、edure parallelapproxtspmas ter (w)begin(1)任意選定i hamilton圈,將圈上的頂點(diǎn)順次記為v、,?、，則該圈為c = vlv2,v2v3,-,%-兒，叩(2) 將c發(fā)送給每個(gè)從進(jìn)程kq <k<n)(3) while true do(3. 1)從每個(gè)從進(jìn)程kq <k<n)接收z(3. 2) avv = minaw. <k<n,(3. 3) ifw = 0 then /*沒有任何改進(jìn)*/向所有從進(jìn)程發(fā)送終止信號return celse將m發(fā)送到各處理器end ifend whileend /* pra 11 elap

32、proxtspmas ter */(2)從進(jìn)程算法procedure para 11 el a pprox tsps la vebegin /*設(shè)當(dāng)前從進(jìn)程的編號為kqukwn) */(1) 從主進(jìn)程接收ha mil ton圈,將圈上的頂點(diǎn)順次記為片，叫，vv，則該圈為c = 兒冬，忖3，兒-1兒，訕(2) accomplished = false(3) while not accomplished do(3. 1) for all 1 < z, j < v h. j -i> doif (i + j) mod n = k thentemp = (iv(v., v/+1) +

33、vv(vy, vy.+1)-(vv(v. ,v.) + w(vi+, v .+1)if temp > aw* thena 叭=tempp = iend ifend ifend for(3.2) c = (c-vpvp+i,v+1)u譏,vp+lvq+,將新的圈c上的頂點(diǎn)順次記為片，冬,，vv(3. 3)將發(fā)送給主進(jìn)程(3. 4)從主進(jìn)程接收最優(yōu)改良對應(yīng)的處理器編號m(3. 5) if k = 0 thenaccomplished = trueelse if k = m then向其它所有從進(jìn)程發(fā)送改良圈celse從從跡程m接收改良圈cend ifend ifend whi leend /

34、* para 1 lei tsps la ve */mpt源程序請參見所附光盤。小結(jié)木章主要討論了八皇后、sat、裝箱、背包和tsp等經(jīng)典組和優(yōu)化問題的并行算法及其mpt編程實(shí)現(xiàn)。對這些問題讀者如欲進(jìn)一步學(xué)習(xí)可參考文獻(xiàn)1、4和5。參考文獻(xiàn)11.朱洪,陳增武,段振華,周克成編著.算法設(shè)計(jì)和分析.上?？茖W(xué)技術(shù)文獻(xiàn)出版社,19892 . da vis m, putnam h. a computing procedure for quan tifica lion theory. j. of the acm, i960,7: 2012153 . gu xiaodong, chen guoliang, g

35、u jun, huang liusheng, yunjae jung. performance analysis andimprovement for some liner on-line bin -packing a1 go ri th ms. j. of combi na tori al optimization, 2002, 12, 6:4554714 陳國良,吳明,顧鈞.搜索背包問題的并行分支界限算法.計(jì)算機(jī)研究與發(fā)展,2001.6,38 (6): 74c74 5.萬穎瑜,周智,陳國良,顧鈞.sizescale:求解旅行商問題(tsp)的新算法.計(jì)算機(jī)研究與發(fā)展, 2002. 10,

36、39 (10): 12941302附錄八皇后問題并行算法的mpi源程序1.源程序 pqueens. c include <mpi. h> include <stdio. li> define queens 8 define max_soluttons 92 typcdef int bool;const int true = 1; const int false = 0;ready,accomplished,new_ task,terminate；enum msg_ tagenum msg con tentrequest. tag,seed tag,reply_tag,n

37、um_solutions_ tag,solutions_tag；int solutionsmax solutionsqueens;int solution_count - 0;bool colides (int rowl, int coll, int row2, intco 12)return (coll = col2)打 (coll - col2 - rowl - row2)/ / (coll + rowl = co 12 + row2); /* collides */int generate_seed()static int seed = 0;doseed+; while (seed &l

38、t;= queens * queens - 1&& collides (0, seed / queens, 1, seed % queens);if (seed > queens * queens - 1)return 0;elsereturn seed; /* genera te seed */void prin t_ solutions (in t count,int solutionsqueens)int i, j, k;for (i = 0; i < count; i+)printf ("solution %d : nf i + 1);for (j

39、 = 0; j < queens; j+)printf("%d : solutionsij);for (k = 0; k < solutionsij k+十)printfc- 9；printf(* “);for (k = queens - 1;k > solutionsij; k-) ptintf("- ”);print f (n); /* print_solutions */bool is safe (in t chessboardf in t row, in t col)int i;for (i = 0; i < row; i+)if (coll

40、ides (i, chessboardi, row, col)return false; /* for */return true; /* is_safe */void place queens (int chessboard, int row)int i, col;if (row >= queens)/*記錄當(dāng)前解*/for (i = 0; i < queens; i+)solutions solution count i= chessboard i ;solu tion_ coun t +;elsefor (col = 0; col < queens; col+)i f

41、(is_safe (chessboard, row, col)/*在當(dāng)前位置放置一個(gè) 皇后*/ chessboard row = col;/*遞歸放置下一個(gè)皇后*/p lace_ queens (chessboard,row + 1); /* if */ /* for */ /* else */ /* place queens */void sequential_eight_queens ()&sta tus);int chessboard queens;solution_count = 0;place_ queens (chossboard, 0);print solutions (

42、solution_count, solutions);void eight queens master(int nodes)mp/status status;int active slaves = nodes 一 1;int new_task = /w task;int terminate = terminate;int reply;int child;int num_solutions;int seed;while (active slaves)mp1_ rec v (&rcpl y, 1,mpi_intfmp1 any source,reply tag,mpworld, child

43、 = status mpi source;if (reply = accomplished)/*從子進(jìn)程接收并記錄解*/mp1 recv(&num solutions, 1,mpi int,child,num_soluttons_ tag,mpt_co帰world, &status);if (numsolutions > 0)mpt recv (solut ions so lut ioncoun t ,queens * num_solutions,mpt_ int,child, solutions_tag,&s ta tus); solution count +二

44、 num_solutions;request. tag,mpt comm world);seed = genera t e_seed();i f (seed) /*還有新的初始棋盤*/*向子進(jìn)程發(fā)送一個(gè)合法的新棋盤*/mp1_ send(&new_ task, 1,mpt_ intfchild,request. tag,mpi_comm_wrld);mpt_ send(&seed, 1,mp1 lntfchild,seed_tag, mpworld);else /*已求出所有解*/*向子進(jìn)程發(fā)送終止信號*/mp1 sen d(&t ermina t e, 1,mpi int,child,active_ slaves一-; /* while */prin t solutions (solution count, solutions); /* eigh t_ queens_master */void eight_queens_ slave (in t niy_rank) mpi_sta lus status;int ready = ready;int accomplished = accomplished;bool finished = false;int request;int seed;int num solutio