排列組合并行算法的實(shí)現(xiàn)

1、Liaoning Normal University開放實(shí)驗(yàn)室項(xiàng)目研究論文題目:排列組合的并行實(shí)現(xiàn)學(xué)院：計(jì)算機(jī)與信息技術(shù)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)序號(hào)：1班21號(hào)學(xué)號(hào):學(xué)生姓名：指導(dǎo)教師：2011年12月排列組合的并行實(shí)現(xiàn)學(xué)生：指導(dǎo)教師：鄭曉薇 張哲計(jì)算機(jī)與信息技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)09級(jí)摘要：回溯法是一種試探求解的方法：通過(guò)對(duì)問(wèn)題的歸納分析，找出求解問(wèn)題的一個(gè)線 索，沿著這一線索往前試探，若試探成功，即得到解；若試探失敗，就逐步往回退，換 其他路線再往前試探。排列組合是通過(guò)一定的約束條件，以及一定的規(guī)律來(lái)輸出數(shù)字的 幾組排列。排列組合是組合學(xué)最基本的概念。所謂排列，就是指從給定個(gè)數(shù)

2、的元素中取 出指定個(gè)數(shù)的元素進(jìn)行排序。 組合則是指從給定個(gè)數(shù)的元素中僅僅取出指定個(gè)數(shù)的元素, 不考慮排序。排列組合的中心問(wèn)題是研究給定要求的排列和組合可能出現(xiàn)的情況總數(shù)。關(guān)鍵詞：回溯法，排列組合，約束條件Abstract:Back in the law is a test the solution method: through inductive analysis ofproblem, find out the problem solving a clue, along the clues on test, test if successful, namely get soluti on;

3、If the test failure, he gradually back towards the back, cha nge other routes go a test. The permutatio n and comb in atio n is through certa in con stra in ts, and certa in laws to output digital several groups of alig nment. The permutati on and comb in ati on is the comb in ati on of the most bas

4、ic learning concept. The so-called arrangement, is refers to the number of eleme nts from a give n out the eleme nts of the desig nated nu mber order. Comb in ati on mea ns that a given number of elements from the specified number of elements out only, do not con sider sort. To arrange a comb in ati

5、 on of cen ter problems are give n the arran geme nt and study dema nd comb ined the possibility of total.Key words : backtrack ing method ; permutati on and comb in ati on; con stra int con diti on刖言許多問(wèn)題的求解過(guò)程可以通過(guò)搜索問(wèn)題的解空間來(lái)完成，而問(wèn)題的解空間可用狀 態(tài)空間樹來(lái)表示，樹中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)問(wèn)題求解的一個(gè)狀態(tài)。對(duì)于一個(gè)狀態(tài)S,如果由根到S的那條路徑確定了這個(gè)解空間的一個(gè)元組，則稱一

6、個(gè)元組，則稱S為一個(gè)解狀態(tài)。如果樹的搜索方法是深度優(yōu)先的，就成為回溯法。排列組合的規(guī)律是多種多 樣的，此論文的排列組合是在設(shè)置其排列的最大數(shù)和排列的個(gè)數(shù)前提下，通過(guò)回溯法 來(lái)完成其條件的約束，輸出不同的排列，并實(shí)現(xiàn)并行。但是在回溯法的基礎(chǔ)上并行經(jīng) 常會(huì)出現(xiàn)問(wèn)題。所以要實(shí)現(xiàn)某些回溯法程序的并行，需要加在合適的位置上，這樣才 能有效的實(shí)現(xiàn)程序的并行化。一、問(wèn)題提出(一) 背景分析許多要求尋找一組解滿足某些約束條件的最優(yōu)解的問(wèn)題中，回溯法非常有用。但 是隨著問(wèn)題復(fù)雜性的增加，串行回溯搜索往往非常費(fèi)時(shí)，所以為了加快搜索速度，提 高效率。實(shí)現(xiàn)回溯搜索的并行化就具有十分重要的意義。在某些排列組合中，用回溯

7、法來(lái)進(jìn)行數(shù)字序列的排列是非常穩(wěn)定的，但是由于回 溯法是通過(guò)不斷返回根節(jié)點(diǎn)來(lái)尋找最優(yōu)解非常耗時(shí)，所以在回溯的基礎(chǔ)上實(shí)現(xiàn)并行化 更是提高了排列的效率。(二) 排列組合的具體約束條件如下排列：12 13 14 1521 23 24 2531 32 34 3541 42 43 4551 52 53 54輸出以上幾組排列，通過(guò)設(shè)置m=2,n=5來(lái)約束排列中允許出現(xiàn)最大的數(shù)以及一組排 列的個(gè)數(shù)，在每個(gè)排列中，不允許出現(xiàn)相同的數(shù)字，也不允許出現(xiàn)相同的排列。并統(tǒng) 計(jì)其組成排列的個(gè)數(shù)。二、回溯法解決排列組合(一) 串行算法設(shè)計(jì)應(yīng)用回溯法產(chǎn)生排列A(n,m)，設(shè)置一維數(shù)組a，a(i)(i=1,2,.,m)在1n中

8、取值。首 先從a(1)=1開始，逐步給a(i)(1 im)賦值，每一個(gè)a(i)賦值從1開始遞增至n。定 義變量g=1,當(dāng)排列中有相同元素則g=0。若i=m與g=1?同時(shí)滿足，貝U為一組解，用s 統(tǒng)計(jì)解的個(gè)數(shù)后，格式打印輸出這組解。由數(shù)字 1n組成的m位整數(shù)組，其約束條 件是沒有相同數(shù)字。(三) 排列組合串行程序算設(shè)計(jì)其串行代碼如下：#i nclude stdafx.h ”#in clude#i nclude #defi ne N 30void mai n()double begi n,end;begi n=(double)clock();int n,m,aN,i,j,g;long s=0;pr

9、in tf( i nput n (n 10):); scan f(%d,&n);printf( input m(1m=n):); scanf(%d,&m);i=1;ai=1;while(1)g=1;for(j=1;ji;j+)if(aj=ai)g=0;break; /*出現(xiàn)相同元素時(shí)返回*/if(g & i=m)s+;for(j=1;jv=m;j+)printf(%d,aj); /* 輸出一個(gè)排列 */ printf();if(s%10=0) prin tf(n);if(g & i0) ai+;else break;prin tf(n s=%ldn,s);en d=(double)clock(

10、);printf(串行查找的時(shí)間:%f 秒n,(end-begin)/(double)CLOCKS_PER_SEC);(四) 排列組合串行程序運(yùn)行結(jié)果運(yùn)行結(jié)果：(1) 當(dāng) n=5,m=3如圖一圖一 n=5,m=3串行運(yùn)行結(jié)果2）當(dāng) n=6,m=4如圖g=360串行的時(shí)間士 3.109000秒41234125412611324135413641524153415641624163劭65421342154216-42314235423642514253425642611263龍&543124315431643214325432643514352435643614362436545124513451

11、645214S2345264531453245364S6145624S63461246134615452146234625463146324635465146524653巳衛(wèi)耳512451265132513-113樂51425143514E516251635164&21352115216S2315234E23652415243524G&261斃3&2G45212531452215224532653415242用4G3衛(wèi)53C45412E4125416&4215423542G543154324恥5-16154t25tl256伺561456215S2356216315b325634EG415612

12、&643129G124&12&6132C13S1426143G14561526丄5462136214e2is6231t234235G241G2436245&251&253625463126314631563216324&3256341634263456351635263546412641364156 42164236425&431643243564E1645264536512651365146521& 5236524e53i65326534654165426S43Ppocess peturned 23 0x17 ecution tivne : 3-141 s Press any ke* to

13、continue 圖二n=6,m=4串行運(yùn)行結(jié)果三、并行實(shí)現(xiàn)排列組合（一）并行思想通過(guò)并行語(yǔ)言O(shè)penMP來(lái)實(shí)現(xiàn)程序的并行，并行是通過(guò)多核處理器對(duì) CPUS行有效的利用，把一個(gè)程序通過(guò)多線程處理的方式縮短時(shí)間，提高運(yùn)行的效率。Ope nMP的編程模型以線程為基礎(chǔ)，通過(guò)編譯指導(dǎo)語(yǔ)句來(lái)顯示地指導(dǎo)并行化，為 編程人員提供了對(duì)并行化的完整的控制。它是一種面向共享內(nèi)存以及分布式共享內(nèi) 存的多處理器多線程并行編程語(yǔ)言。具有良好的可移植性，支持多種編程語(yǔ)言，能 夠支持多種平臺(tái)，包括大多數(shù)的類UNIX系統(tǒng)以及 WindowsNT系統(tǒng)(Windows2000. Windows XP Windows Vista

14、等)。使用運(yùn)行時(shí)函數(shù)庫(kù)所包含的函數(shù)，必須在相應(yīng)的源文件中包含Ope nM頭文件，即#i nclude “ omp.h”四個(gè)最常用的OpenM!庫(kù)函數(shù)：in t omp_get_num_threads(void) 返回當(dāng)前使用的線程個(gè)數(shù)。in t omp_set_num_threads(i nt NumThreads) 在進(jìn)入并行區(qū)域前，該函數(shù)設(shè)置將要 使用的線程個(gè)數(shù)，它可以覆蓋環(huán)境變量 OMP_NUM_THREADS。int omp_get_thread_num(void) 返回當(dāng)前線程號(hào)，值在0(主線程)到線程總數(shù)減1 之間。int omp_get_num_procs(void)返回可用的處

15、理核(處理器)個(gè)數(shù)。支持超線程技術(shù) 的處理核或處理器將被算作兩個(gè)處理核(或兩個(gè)處理器)。(二) 排列組合并行程序的實(shí)現(xiàn)在該排列組合中有兩個(gè)循環(huán)可以套用變成并行循環(huán)，但其中一個(gè)中有break跳出無(wú)法執(zhí)行并行，所以就用另一個(gè)循環(huán)來(lái)進(jìn)行并行循環(huán)。其核心代碼如下：s+;omp_set_ num _threads(4) #pragma omp parallel for for(j=1;j=m;j+) /*輸出一個(gè)排列*/pri ntf(%d,aj); printf();if(s%10=0) prin tf(n);(三) 并行程序運(yùn)行結(jié)果(1) 當(dāng) n=5,m=3如圖三123124125132134U.5

16、3154213214215245251253254312341342345351352423425431432435514521523S24531匚 F:pnjeciinput n n ：5 in put：3s=t0并行的時(shí)間：2-07800B秒13514214314515223123423524124331131521324325354-112413415421451524S3512513532534541542543Process returned 23 Pres any Ikey to continue Bexecuition time 2 -109 s圖三n=5,m=3并行運(yùn)行結(jié)果(2

17、)當(dāng) n=6,m=4如圖四EF： project sbin Debug se123 4125412641324135413641524153415641624163 41654Z134Z1542164231423542364251-1253425& 426142634Z&S4312431543164321432543264351 4352435643&143&2436545124513451645214523 452645314S32453G456145624563461246134615 45214&234&Z5463146324635465146524653B123 5124S126513

18、2513451365142514351465162<3 S164S213521452165231&234S23&S24152435246 526152&352&4E312531453165321532453265341 5342534653&15362S36454125413541651215423 542651315432&43654&1546254635&125&13EG14 521St23S2456315G32&6345841SG42g&43123 G124 直2 &122 &134&142 6143 &145 1526153 6154&213&214&215&231&2362356

19、241243“45 6251&253&254&312G314631563216926325b341 G342G?4gG3516354G412G413G415421&423 642Gt4Jl&422&435451G45264G?65126512514 6&2152365246531&53265346541&5426543s=369并行的時(shí)間匸2-718000秒Process i-e turned 23 execution time = 3,047 sPress iiny key to continue.圖四n=6,m=4并行運(yùn)行結(jié)果四、并行運(yùn)行結(jié)果與串行運(yùn)行結(jié)果分析程序運(yùn)行加速比：串行執(zhí)行時(shí)間/并行執(zhí)行時(shí)間m時(shí)間(s)時(shí)間(s)時(shí)間(s)平均時(shí)間加速比串行n=931.91.71.9M.831.3343.4062.9843.3433.24458.2507.8128.4688.1751.36628.37530.84432.203:30.4747105.875106.48499.093103.8171.24并行n=931.2031.5311.3751.36942.4532.1562.5002.3691.0656.5626.4846.6706.572628.02329.37528.62528.6742.06757