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

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

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

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

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

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

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

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

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

9、必進(jìn)行任何合并操作就已經(jīng)排好序了。</p><p>　　算法實(shí)現(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}進(jìn)行快速排序。</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); //對(duì)左半段排序</p><p>　　quick_sort(data,q+1,r); //對(duì)右半段排序</p><p><b>　　} </b></p><p>　　int main() </p><p><b>　　{ </b></p

16、><p>　　int i,n,data[size];</p><p>　　printf("請(qǐng)輸入要排列的數(shù)目（<=20）：");</p><p>　　scanf("%d",&n);</p><p>　　printf("請(qǐng)輸入要排列的數(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>　　運(yùn)行結(jié)果如下：</b></p><p><b>　　圖1</b></p><p><b>　　圖5</b></p><p>　　回溯法—0-1背包問(wèn)題</p><p>　　回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問(wèn)題的所有解的解空間樹中

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

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

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

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

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

25、i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說(shuō)明"剛剛"裝入背包的那件物品"不合適"，應(yīng)將它取出"棄之一邊"，繼續(xù)再?gòu)?quot;它之后"的物品中選取，如此重復(fù)，直至求得滿足條件的解。因?yàn)榛厮萸蠼獾囊?guī)則是"后進(jìn)先出"，所以要用到棧來(lái)存儲(chǔ)符合

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

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

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

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

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

31、題的解空間；</p><p>　　2.確定易于搜索的解空間結(jié)</p><p>　　3.以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索；</p><p><b>　　5 算法實(shí)現(xiàn)</b></p><p>　　運(yùn)用Pc機(jī)，C/C++程序?qū)W習(xí)系統(tǒng)軟件 編程C語(yǔ)言</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<<"輸入物品價(jià)值:";</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)價(jià)值：";</p><p>　　cout<<b.bestp<<endl;</p><p><b>　　}</b></p><p&g

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

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

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

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

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

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