課程設(shè)計--用分治法解決快速排序問題及用回溯法解決0-1背包問題

1、<p>　　用分治法解決快速排序問題及用回溯法解決0-1背包問題</p><p><b>　　課程設(shè)計目的：</b></p><p>　　《計算機算法設(shè)計與分析》這門課程是一門實踐性非常強的課程，要求我們能夠?qū)⑺鶎W(xué)的算法應(yīng)用到實際中，靈活解決實際問題。通過這次課程設(shè)計，能夠培養(yǎng)我們獨立思考、綜合分析與動手的能力，并能加深對課堂所學(xué)理論和概念的理解，可以訓(xùn)練我

2、們算法設(shè)計的思維和培養(yǎng)算法的分析能力。</p><p><b>　　二、課程設(shè)計內(nèi)容：</b></p><p><b>　　1、分治法：</b></p><p><b>　　（2）快速排序；</b></p><p><b>　　2、回溯法：</b><

3、/p><p><b>　　（2）圖的著色。</b></p><p><b>　　三、概要設(shè)計：</b></p><p><b>　　分治法—快速排序：</b></p><p>　　分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞

4、歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。分治法的條件：</p><p>　　該問題的規(guī)?？s小到一定的程度就可以容易地解決；</p><p>　?。?) 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；</p><p>　?。?) 利用該問題分解出的子問題的解可以合并為該問題的解；</p><p>　?。?/p>

5、4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。</p><p>　　抽象的講，分治法有兩個重要步驟：</p><p><b>　?。?）將問題拆開；</b></p><p><b>　?。?）將答案合并；</b></p><p>　　回溯法—0-1背包問題</

6、p><p>　　回溯法的基本思想是確定了解空間的組織結(jié)構(gòu)后，回溯法就是從開始節(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始節(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的或節(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前的擴展結(jié)點就成為死結(jié)點。換句話說，這個節(jié)點，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回（

7、回溯）移動至最近一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸的在解空間中搜索，直到找到所要求的解或解空間中以無活結(jié)點為止。</p><p>　　四、詳細設(shè)計與實現(xiàn)：</p><p><b>　　分治法—快速排序</b></p><p>　　快速排序是基于分治策略的另一個排序算法。其基本思想是，對于輸入的子數(shù)組,按以

8、下三個步驟進行排序：</p><p>　?。?）、分解(divide) 以元素為基準元素將劃分為三段，和，使得中任何一個元素都小于，而中任何一個元素大于等于，下標(biāo)在劃分過程中確定。</p><p>　　（2）、遞歸求解(conquer) 通過遞歸調(diào)用快速排序算法分別對和進行排序。</p><p>　?。?）、合并(merge) 由于和的排序都是在原位置進行的，所以不

9、必進行任何合并操作就已經(jīng)排好序了。</p><p>　　算法實現(xiàn)題: 現(xiàn)將數(shù)列{12 21 31 45 36 76 66 46 30 7 89 20 2 5 99 47 23 54 51 73}進行快速排序。</p><p><b>　　源程序如下：</b></p><p>　　#include <i

10、ostream></p><p>　　using namespace std;</p><p>　　#define size 20 </p><p>　　int partition(int data[],int p,int r) </p><p><b>　　{ </b></p><p>　

11、　int n=data[p],i=p+1,j=r,temp; </p><p>　　//將<n的元素交換到左邊區(qū)域</p><p>　　//將>n的元素交換到右邊區(qū)域</p><p>　　while(true) </p><p><b>　　{ </b></p><p>　　while

12、(data[i]<n) ++i; </p><p>　　while(data[j]>n) --j;</p><p><b>　　if(i>=j) </b></p><p><b>　　break; </b></p><p>　　temp=data[i]; data[i]=data

13、[j]; data[j]=temp; </p><p><b>　　} </b></p><p>　　data[p]=data[j]; </p><p>　　data[j]=n; </p><p>　　return j; </p><p><b>　　}</b></

14、p><p>　　void quick_sort(int data[],int p,int r) </p><p>　　{ if(p>=r) </p><p><b>　　return; </b></p><p>　　int q=partition(data,p,r); </p><p&

15、gt;　　quick_sort(data,p,q-1); //對左半段排序</p><p>　　quick_sort(data,q+1,r); //對右半段排序</p><p><b>　　} </b></p><p>　　int main() </p><p><b>　　{ </b></p

16、><p>　　int i,n,data[size];</p><p>　　printf("請輸入要排列的數(shù)目（<=20）：");</p><p>　　scanf("%d",&n);</p><p>　　printf("請輸入要排列的數(shù)列：\n");</p>&

17、lt;p>　　for(i=0;i<n;++i) </p><p>　　scanf("%d",&data[i]); </p><p>　　quick_sort(data,0,n-1);</p><p>　　printf("排列后的數(shù)列為：\n"); </p><p>　　for

18、(i=0;i<n;++i) </p><p>　　printf( "%d ",data[i]); </p><p>　　printf("\n");</p><p>　　return 0; </p><p><b>　　} </b></p><

19、;p><b>　　運行結(jié)果如下：</b></p><p><b>　　圖1</b></p><p><b>　　圖5</b></p><p>　　回溯法—0-1背包問題</p><p>　　回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中

20、，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回

21、溯法，它適用于解一些組合數(shù)較大的問題。 二、算法框架： 1、問題的解空間：應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)到少包含問題的一個（最優(yōu)）解。 2、回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為

22、一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱</p><p><b>　　1 問題描述</b></p><p>　　對于0-1背包問題回溯法的一個實例，n=4，c=7，p=[9,10,7,4],w=[3,5,2,1].這4個物品的單位重量價值分別為[3,2,3,5,4].以物品為單位價值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這

23、3個物品后，剩余的背包容量為1，只能裝入0.2的物品2.由此可得到一個解為x=[1,0,2,1,1],其相應(yīng)的價值為22.盡管這不是一個可行解，但可以證明其價值是最有大的上界。因此，對于這個實例，最優(yōu)值不超過22. 回溯法的基本思想是按深度優(yōu)先策略，從根節(jié)點出發(fā)搜索解空間樹，算法搜索至解空間的任一點時，先判斷該結(jié)點是否包含問題的解，如果肯定不包含，則跳過以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯，否則，進入該子樹，繼續(xù)按深度優(yōu)先進行

24、搜索。</p><p><b>　　2 問題分析</b></p><p>　　利用回溯法的設(shè)計思想來解決背包問題。首先是將可供選擇的物品的個數(shù)輸入程序，將物品排成一列，計算總物品的體積s，然后輸入背包的實際體積V，如果背包的體積小于0或者大于物品的總體積s，則判斷輸入的背包體積錯誤，否則開始順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第

25、i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明"剛剛"裝入背包的那件物品"不合適"，應(yīng)將它取出"棄之一邊"，繼續(xù)再從"它之后"的物品中選取，如此重復(fù)，直至求得滿足條件的解。因為回溯求解的規(guī)則是"后進先出"，所以要用到棧來存儲符合

26、條件的解，在存儲過程中，利用數(shù)組來存儲各個物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧里，最后得到符合條件的解并且實現(xiàn)輸出。</p><p><b>　　3 建立數(shù)學(xué)模型 </b></p><p>　　0-l背包問題是子集選取問題。一般情況下，0-1背包問題是NP難題。0-1背包問題的解空間可用子集樹表示。解0-1背包問題的回溯法與裝載問

27、題的回溯法十分類似。在搜索解空間樹時，只要其左兒子結(jié)點是一個可行結(jié)點，搜索就進入其左子樹。當(dāng)右子樹有可能包含最優(yōu)解時才進入右子樹搜索。否則將右子樹剪去。設(shè)r是當(dāng)前剩余物品價值總和；cp是當(dāng)前價值；bestp是當(dāng)前最優(yōu)價值。當(dāng)cp+r≤bestp時，可剪去右子樹。計算右子樹中解的上界的更好方法是將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是右子樹中解的上界。算法復(fù)雜性是算法

28、運行所需要的計算機資源的量，需要時間資源的量稱為時間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，則有： T=T(N,I)和S=S(N,I) 。</p><p>　　最壞情況下

29、的時間復(fù)雜性：</p><p>　　最好情況下的時間復(fù)雜性：</p><p>　　平均情況下的時間復(fù)雜性：</p><p>　　其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N, I*)達到Tmax(N)的合法輸入； 是中使T(N, )達到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。</p><p>&l

30、t;b>　　4 算法設(shè)計</b></p><p>　　使用棧作為該程序的數(shù)據(jù)結(jié)構(gòu)，利用棧進行語法檢查，以深度優(yōu)先的搜索方式解空間，實現(xiàn)遞歸過程和函數(shù)的調(diào)用，在設(shè)計時還使用C語言的數(shù)組及其循環(huán)語言來實現(xiàn)程序。運用回溯法解題，在搜索解空間樹時，只要其左兒子節(jié)點是一個可行結(jié)點，搜索就進入左子樹，在右子樹中有可能包含最優(yōu)解是才進入右子樹搜索。否則將右子樹剪去。具體步驟如下：1.針對所給問題，定義問

31、題的解空間；</p><p>　　2.確定易于搜索的解空間結(jié)</p><p>　　3.以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；</p><p><b>　　5 算法實現(xiàn)</b></p><p>　　運用Pc機，C/C++程序?qū)W習(xí)系統(tǒng)軟件 編程C語言</p><p>&

32、lt;b>　　程序源代碼</b></p><p><b>　　核心源代碼</b></p><p>　　#include <iostream.h></p><p>　　struct bag</p><p><b>　　{</b></p><p>&

33、lt;b>　　double w;</b></p><p>　　double cw,cp,bestp;</p><p><b>　　};</b></p><p>　　struct goods</p><p><b>　　{</b></p><p>　　doub

34、le wc,pc;int v;</p><p><b>　　}; </b></p><p>　　void paixu(goods g[],int n)</p><p><b>　　{</b></p><p>　　int i,j;double temp;</p><p>　　f

35、or(i=0;i<n-1;i++)</p><p><b>　　{</b></p><p>　　for(j=n-1;j>i;j--)</p><p><b>　　{</b></p><p>　　if((g[j].pc/g[j].wc)>(g[j-1].pc/g[j-1].wc))&

36、lt;/p><p><b>　　{</b></p><p>　　temp=g[j].pc;</p><p>　　g[j].pc=g[j-1].pc;</p><p>　　g[j-1].pc=temp;</p><p>　　temp=g[j].wc;</p><p>　　g[j]

37、.wc=g[j-1].wc;</p><p>　　g[j-1].wc=temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b

38、></p><p>　　void backtruck(int i,int n,goods g[],bag *b)</p><p><b>　　{</b></p><p>　　if(i>=n&&b->cw<=b->w)</p><p><b>　　{</b>

39、;</p><p>　　if(b->bestp<b->cp)</p><p>　　b->bestp=b->cp;</p><p><b>　　}</b></p><p>　　if(i<n&&b->cw<=b->w)</p><p&g

40、t;<b>　　{</b></p><p>　　b->cw=b->cw+g[i].wc;</p><p>　　b->cp=b->cp+g[i].pc;</p><p>　　backtruck(i+1,n,g,b);</p><p>　　b->cw=b->cw-g[i].wc;</

41、p><p>　　b->cp=b->cp-g[i].pc;</p><p>　　backtruck(i+1,n,g,b);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p>

42、<p><b>　　{</b></p><p>　　goods g[100];</p><p><b>　　bag b;</b></p><p><b>　　int n,i;</b></p><p>　　cout<<"輸入背包容量:";

43、</p><p><b>　　cin>>b.w;</b></p><p>　　cout<<"物品數(shù)量:";</p><p><b>　　cin>>n;</b></p><p>　　cout<<"輸入物品的質(zhì)量:"

44、;</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p><b>　　g[i].v=1;</b></p><p>　　cin>>g[i].wc;</p><p><b>　　}</b&g

45、t;</p><p>　　cout<<"輸入物品價值:";</p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b></p><p><b>　　g[i].v=1;</b></p><p>　　cin&

46、gt;>g[i].pc;</p><p><b>　　}</b></p><p>　　paixu(g,n);</p><p>　　b.bestp=0;</p><p><b>　　b.cw=0;</b></p><p><b>　　b.cp=0;</b&

47、gt;</p><p>　　backtruck(0,n,g,&b);</p><p>　　cout<<"最優(yōu)價值：";</p><p>　　cout<<b.bestp<<endl;</p><p><b>　　}</b></p><p&g

48、t;<b>　　6 測試分析</b></p><p>　　1.當(dāng)輸入的背包體積V小于物品的總體積s 時：</p><p>　　2.當(dāng)輸入的背包體積V大于物品的總體積s 時：</p><p>　　當(dāng)輸入的背包體積小于等于可供選擇的物品的總體積時，可以正確進行選擇裝入的物品，并且統(tǒng)計符合條件的解的方法；當(dāng)輸入的背包體積小于0或者大于可供選擇的物品的

49、總體積時，程序會自動提醒輸入背包體積錯誤，這樣就方便了程序的正確運行與解決實際問題的重要作用。</p><p><b>　　實驗結(jié)果</b></p><p><b>　　五、總結(jié)：</b></p><p>　　通過本次課程設(shè)計，使我對快速排序以及0-1背包設(shè)計的基本過程的設(shè)計方法、步驟、思路、有了一定的了解與認識。在這次課

50、程設(shè)計過程中，我認識到只是知道課本上的理論知識是遠遠不夠的，我們還必須要深切的理解每個算法的思想，并且能夠利用c++語言去編寫相關(guān)的代碼，經(jīng)過不斷的修改、調(diào)試，使之能解決相應(yīng)的問題，最終能運用到實際案例中去。 </p><p>　　本程序利用回溯法的設(shè)計思想來解決問題，在用來求問題的所有解時，針對所給問題，定義問題的解空間，確定易于搜索的解空間結(jié)構(gòu)，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束，回溯法的求解規(guī)

51、則是后進先出，所以在程序設(shè)計中自然要使用到了棧。在程序設(shè)計過程中，更加鞏固了我的C語言程序設(shè)計基礎(chǔ)知識，使我對C語言的循環(huán)操作和指針、數(shù)組操作更加熟悉，區(qū)別了棧與鏈表，學(xué)會用棧來解決實際問題，并且聯(lián)系了樹的重要內(nèi)容，重點訓(xùn)練了對算法與數(shù)據(jù)結(jié)構(gòu)的難點內(nèi)容，算法與數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一，使編程語言更加簡潔，清晰易懂，強調(diào)了好的程序設(shè)計風(fēng)格,運行結(jié)果更加美觀，在調(diào)試和運行時，我遇到了一些很基礎(chǔ)的問題，通過請教老師和同學(xué)，這些問題都逐一解決了，這使得我

52、在運行正確通過時，內(nèi)心產(chǎn)生了一種很強烈的成就感，因此提高了我對編程的濃厚興趣，更加增強了自己學(xué)習(xí)好計算機語言的信心。</p><p><b>　　參考文獻</b></p><p>　　[1]黃迪明，余勤 等編著. C語言程序設(shè)計教程[M].國防工業(yè)出版社1999.</p><p>　　[2]陳媛等編著.  算法與數(shù)

53、據(jù)結(jié)構(gòu)[M]. 清華大學(xué)出版社 2002 .</p><p>　　[3]王曉東編著.計算機算法設(shè)計與分析[M].北京：電子工業(yè)出版社，2007.5</p><p>　　[4]余祥宣,崔國華,鄒海明.計算機算法基礎(chǔ)[M].武漢:華中科技大學(xué)出版社,2000． </p><p>　　[5]盧開澄.計算機算法導(dǎo)引—設(shè)計與分析[M].北京:清華大學(xué)出版社,2003