用分治法解決快速排序問題及用動態(tài)規(guī)劃法解決最優(yōu)二叉搜索樹問題及用回溯法解決圖的著色問題

用分治法解決快速排序問題及用動態(tài)規(guī)劃法解決最優(yōu)二叉搜索樹問題及用回溯法解決圖的著色問題一、課程設(shè)計(jì)目的：《計(jì)算機(jī)算法設(shè)計(jì)與分析》這門課程是一門實(shí)踐性非常強(qiáng)的課程，要求我們能夠?qū)⑺鶎W(xué)的算法應(yīng)用到實(shí)際中，靈活解決實(shí)際問題。通過這次課程設(shè)計(jì)，能夠培養(yǎng)我們獨(dú)立思考、綜合分析與動手的能力，并能加深對課堂所學(xué)理論和概念的理解，可以訓(xùn)練我們算法設(shè)計(jì)的思維和培養(yǎng)算法的分析能力。二、課程設(shè)計(jì)內(nèi)容：1、分治法：（2）快速排序；2、動態(tài)規(guī)劃：（4）最優(yōu)二叉搜索樹；3、回溯法：（2）圖的著色。三、概要設(shè)計(jì)：分治法—快速排序：分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題些子問題，然后將各個(gè)子問題的解合并得到原問題的相同。遞歸地解這解。分治法的條件：（1)問該題的規(guī)?？s小到一定的程（2)問該題可以分解為若干個(gè)規(guī)模較小的（3)利用問該題分解出的子問題的解可以合并為問該題的解；（4)問該題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。抽象的講，分治法有兩個(gè)重要步驟：（1）將問題拆開；（2）將答案合并；度就可以容易地解決；相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；

《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告動態(tài)規(guī)劃—最優(yōu)二叉搜索樹：動態(tài)規(guī)劃的基本思想是將問題分解為若干個(gè)小問題，解子問題，然后從子問題得到原問題的解。設(shè)計(jì)動態(tài)規(guī)劃法的步驟：（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（2）遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；（3）以自底向上的方式計(jì)算出最優(yōu)值；（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解?；厮莘ā獔D的著色回溯法的基本思想是確定了解空間的組織結(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)就成為死結(jié)點(diǎn)。換句話說，這個(gè)節(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，回（回溯）移動至最近一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸的在解空間中搜索，直到找到所要求的解或解空間中以無活結(jié)點(diǎn)為止。則應(yīng)往四、詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)：分治法—快速排序快速排序是基于分治策略的另一個(gè)排序算法。其基本思想是，對于輸入的子數(shù)組apr:,按以下三個(gè)步驟進(jìn)行排序：（1）、分解(divide)以元素ap為基準(zhǔn)元素將apr:劃分為三段ap:q1aq，1:aq1:r中任何一個(gè)元素中任何一個(gè)元素都小于，而aq和，aqr使得ap:q1大于等于，下標(biāo)在劃分q過程中確定。aq（2）、遞歸求解(conquer)通過遞歸調(diào)用快速排序算法分別對ap:q1aq和1:r進(jìn)行排序。1:r的排序都是在原位置進(jìn)行的，所以不（3）、合并(merge)由于ap:q1aq和必進(jìn)行任何合并操作就已經(jīng)排好序了。算法實(shí)現(xiàn)題:現(xiàn)將數(shù)列{23213445657686463039892022《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告384738545940}進(jìn)行快速排序。源程序如下：#include<iostream>usingnamespacestd;#definesize20intpartition(intdata[],intp,intr){intn=data[p],i=p+1,j=r,temp;//將<n的元素交換到左邊區(qū)域//將>n的元素交換到右邊區(qū)域while(true){while(data[i]<n)++i;while(data[j]>n)--j;if(i>=j)break;temp=data[i];data[i]=data[j];data[j]=temp;}data[p]=data[j];data[j]=n;returnj;}voidquick_sort(intdata[],intp,intr){if(p>=r)return;intq=partition(data,p,r);quick_sort(data,p,q-1);//對左半段排序quick_sort(data,q+1,r);//對右半段排序}intmain()3{inti,n,data[size];printf("請輸入要排列的數(shù)目（<=20）：");scanf("%d",&n);printf("請輸入要排列的數(shù)列：\n");for(i=0;i<n;++i)scanf("%d",&data[i]);quick_sort(data,0,n-1);printf("排列后的數(shù)列為：\n");for(i=0;i<n;++i)printf("%d",data[i]);printf("\n");return0;}運(yùn)行結(jié)果如下：圖1動態(tài)規(guī)劃—最優(yōu)二叉搜索樹1、最優(yōu)二叉搜索樹問題描述和分析：設(shè)Sxx,,,x是有序集，且xxnx，表示有序集S的二叉搜索樹利12n12用二叉樹的結(jié)點(diǎn)存儲有序集中的元素。它具有下述性質(zhì)：存儲于每個(gè)結(jié)點(diǎn)中的元素x大于其4《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告左子樹中任一結(jié)點(diǎn)所存儲的元素，小于其右子樹中任一結(jié)點(diǎn)所存儲的元素。二叉樹的葉結(jié)點(diǎn)x,x的開區(qū)間，在表示是形如S的二叉搜索樹中搜索元素x，返回的結(jié)果有兩種情況：ii1xx。（1）在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到i（2）在二叉搜索樹的葉結(jié)點(diǎn)中確定xx,x。ii1xx,xii1設(shè)在第(1)中情形中找到元素xx的概率為；在第b(2)種情形中確定的iia。其中約定x,x。顯然有：概率為i0n1a0,0in;b0,1jn;nnb1jaijii0a,b,a,,b,a稱為集合S的存取概率分布。j1011nn在表示S的二叉搜索樹T中，設(shè)存儲元素x的結(jié)點(diǎn)深度為c；葉結(jié)點(diǎn)x,x的結(jié)點(diǎn)iijj1深度為d，則：jpnb1cinadjiji1j0表示在二叉搜索樹T中進(jìn)行一次搜索所需要的平均比較次數(shù)，p又成為二叉搜索樹T的平均路長。在一般情況下，不同的二叉搜索樹的平均路長是不相同的。S及其存取概率分布ababa，在所有,,,,,最優(yōu)二叉搜索樹問題是對于有序集011nn表示有序集S的二叉搜索樹中找到一棵具有最小平均路長的二叉搜索樹。2、最優(yōu)子結(jié)構(gòu)性質(zhì)：x,x,,x,xi1j1ij,,x和葉結(jié)點(diǎn)j二叉搜索樹T的一棵含有結(jié)點(diǎn)xi的子樹可以看作是有序集xx關(guān)于全集合j,,x,,xi1j1的一棵二叉搜索樹，其存取概率為以下的i條件概率：bb/wikjkkijaa/wi1hjhhijwa式中，ijbba,1ijn。ijji15《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告a,b,,b,a的一棵最優(yōu)二叉搜索樹，設(shè)T是有序集xx關(guān)于存取概率ij,,iji1ijj其平均路長為T和T的平均路長分別為p。T的根結(jié)點(diǎn)存儲元素x。其左右子樹p和ijijmlrlp。由于T和T中結(jié)點(diǎn)深度是它們在T中的結(jié)點(diǎn)深度減1，故有：rrlijwpwwpwlpi,ji,ji,ji,m1m1,jrT是關(guān)于集合x,,x的一棵二叉搜索樹，故pp。若pp由于，則i,m1im1li,m1ll用T替換i,m1T可得到平均路長比T更小的二叉搜索樹。這與T是最優(yōu)二叉搜索樹矛盾。ijijl故T是一棵最優(yōu)二叉搜索樹。同理可證T也是一棵最優(yōu)二叉搜索樹。因此最優(yōu)二叉搜索樹lr問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3、遞歸計(jì)算最優(yōu)值：最優(yōu)二叉搜索樹T的平均路長為p，則所求的最優(yōu)值為p。由最優(yōu)二叉搜索樹問題1,nijij的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計(jì)算p的遞歸式如下：ijmin,ijwpwi,ji,jwpwpk1,jk1,ji,ji,k1i,k1ikj0,1in。初始時(shí)，pi,i1記wp為mij，則m1,nwpp為所求的最優(yōu)值。1,n1,n1,n,i,ji,j,mij的遞歸式為：計(jì)算mi,k1mk1,j,ijminmi,jwi,jikjmi,i10,1in據(jù)此，可設(shè)計(jì)出解最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法。算法實(shí)現(xiàn)題:給出標(biāo)識符集{1,2,3}={do,if,stop}存取概率，若b1=0.4b2=0.2b3=0.05a0=0.2a1=0.05a2=0.05a3=0.05構(gòu)造一棵最優(yōu)二叉搜索樹源程序如下：#include<iostream>usingnamespacestd;voidOptimalBinarySearchTree(floata[],floatb[],intn,floatm[][20],ints[][20],floatw[][20])6《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告{//求解最優(yōu)值的方法inti,r,k;floatt;for(i=0;i<=n;i++){w[i+1][i]=a[i];m[i+1][i]=0;}//搜索不到的點(diǎn),最優(yōu)解為0for(r=0;r<n;r++)for(i=1;i<=n-r;i++){intj=i+r;//左子樹為空w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i+1][j];s[i][j]=i;for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j];if(t<m[i][j]){//以k為根節(jié)點(diǎn)，左子樹不為空m[i][j]=t;s[i][j]=k;}}m[i][j]+=w[i][j];}for(i=1;i<=n;i++)for(intj=1;j<=n;j++)cout<<"s["<<i<<"]["<<j<<"]="<<s[i][j]<<endl;}voidprint(inti,intj,ints[][20],intS[])//遞歸輸出結(jié)果{if(j>=i){intk=s[i][j];7《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告cout<<"(";print(i,k-1,s,S);cout<<")";cout<<""<<S[k]<<"";cout<<"(";print(k+1,j,s,S);cout<<")";}}intmain(){//主函數(shù)intn,i;floata[20],b[20],m[20][20],w[20][20];ints[20][20],S[20];cout<<"請輸入有序集元素的個(gè)數(shù)n："<<endl;cin>>n;cout<<"請輸入有序集各元素的值S[i](一共"<<n<<"個(gè)):"<<endl;for(i=1;i<=n;i++)cin>>S[i];cout<<"請輸入概率數(shù)組a的各元素的值a[i](一共"<<n+1<<"個(gè)):"<<endl;for(i=0;i<=n;i++)cin>>a[i];cout<<"請輸入概率數(shù)組b的各元素的值b[i](一共"<<n<<"個(gè)):"<<endl;for(i=1;i<=n;i++)cin>>b[i];OptimalBinarySearchTree(a,b,n,m,s,w);cout<<"最優(yōu)值即平均步長為："<<m[1][n]<<endl;}運(yùn)行結(jié)果如下：8圖2回溯法—圖的著色1、圖的m著色問題描述：G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色。這個(gè)問題是圖的m可著色判定問題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù)m為該圖2、算法設(shè)計(jì)：給定無向連通圖的色數(shù)。求一個(gè)圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。,GVE和m種顏色，如果這一般連通圖的可著色法問題并不僅限于平面圖。給定圖個(gè)圖不是m可著色，則給出否定答案；如果這個(gè)圖是m可著色的，找出所有不同的著色方法下面根據(jù)回朔法的遞歸描述框架Backtrack設(shè)計(jì)圖的m著色算法。用圖的鄰接矩陣aaij1，否則,i,jGVE。若屬于圖的邊集E，則GV,E表示無向量連通圖aij0。整數(shù)1，2，…，m用來表示m種不同顏色。頂點(diǎn)i所有顏色用xi表示，數(shù)組x1:n是問題的解向量。問題的解空間可表示為一棵高度為n+1的完全m叉樹。解空間樹的第i1in層中每一結(jié)點(diǎn)都有m個(gè)兒子，每個(gè)兒子相應(yīng)于xi的m個(gè)可能的著色一之。第n+1層結(jié)點(diǎn)均為葉結(jié)點(diǎn)。9《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告在下面的解圖的m可著色問題的回溯法中，類Color的數(shù)據(jù)成員記錄解空間中前已找到的m著色方案數(shù)。Backtracki搜索解空間中第i層子樹。結(jié)點(diǎn)信息，以減少傳給Backtrack的參數(shù)。sum記錄當(dāng)Backtrack中，當(dāng)in時(shí)，算法搜索m著色方案數(shù)sum則增1。而當(dāng)in時(shí),當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)解空間中內(nèi)部結(jié)點(diǎn).在算法至葉結(jié)點(diǎn)，得到新的m著色方案，當(dāng)前找到的該結(jié)點(diǎn)有xi1,2,,m共m個(gè)兒子結(jié)點(diǎn).對當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一兒子結(jié)點(diǎn),有方法ok檢行性,并以深度優(yōu)先的方式遞歸的對可行子樹搜索,或減去不可行樹。一個(gè)無向連通圖G，現(xiàn)有4種不同的顏色，用這4種一種顏色。要求：G中每條邊的2個(gè)頂點(diǎn)著查其可算法實(shí)現(xiàn)題:給定如圖3所示的顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著有不同的顏色。問一共有多少種著色方案？13425圖3源程序如下：#include<iostream>usingnamespacestd;intn;//圖的頂點(diǎn)個(gè)數(shù)intm;//可用顏色數(shù)inti,j;inta[10][10];intx[10];//程序中使用時(shí)從下標(biāo)1開始;程序中用于存儲圖的鄰接矩陣//用于存儲當(dāng)前解longsum;//當(dāng)前已找到的可著色方案數(shù)10《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告boolOk(intk){for(intj=1;j<=n;j++){if((a[k][j]==1)&&(x[j]==x[k]))//a[k][j]==1表示的是第k點(diǎn)和第j點(diǎn)是相連的returnfalse;}returntrue;}voidBacktrack(intt){if(t>n){//t是表示的第t行葉結(jié)點(diǎn)；圖的m著色共有n個(gè)結(jié)點(diǎn)sum++;cout<<"第"<<sum<<"種解決方案為：\n";for(inti=1;i<=n;i++){cout<<x[i]<<"";}cout<<endl;}else{for(inti=1;i<=m;i++){x[t]=i;if(Ok(t)){Backtrack(t+1);//判斷t+1結(jié)點(diǎn)的顏色是不是正確}11《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告x[t]=0;//把t+1結(jié)點(diǎn)的顏色換一種}}}longmColoring(intmm){m=mm;sum=0;Backtrack(1);returnsum;}voidmain(){cout<<"\n\t==========圖的m著色問題============\n";cout<<"輸入圖的頂點(diǎn)數(shù)與可用的顏色數(shù):\n";cin>>n>>m;cout<<"\n==========輸入圖的鄰接矩陣\n";for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>a[i][j];cout<<"\n==========判斷可著色性\n";mColoring(m);if(sum==0)cout<<"無可行方案！"<<endl;cout<<"-------------------------------------------------------------------------------"<<endl;cout<<n<<"個(gè)頂點(diǎn)"<<"按所給的鄰接關(guān)系著"<<m<<"種顏色，總的著色方案有"<<sum<<"個(gè)\n";}運(yùn)行結(jié)果如下：12圖4圖5五、總結(jié)：通過本次課程設(shè)計(jì)，使我對快速排序、最優(yōu)二叉搜索樹以及圖的m著色設(shè)計(jì)的基本過程的設(shè)計(jì)方法、步驟、思路、有了一定的了解與認(rèn)識。在這次課程設(shè)計(jì)過程中，我認(rèn)識到只是知道課本上的理論知識是遠(yuǎn)遠(yuǎn)不夠的，我們還必須要深切的理解每個(gè)算法的思想，并且能夠利用c++語言去編寫相關(guān)的代碼，經(jīng)過不斷的修改、調(diào)試，使之能解決相應(yīng)的問題，最終13《計(jì)算機(jī)算法設(shè)計(jì)與分析》課程設(shè)計(jì)報(bào)告能運(yùn)用到實(shí)際案例中去。對我們來說，實(shí)際能力的培養(yǎng)至關(guān)重要，而這種實(shí)際能力的培養(yǎng)單靠課堂教學(xué)是遠(yuǎn)遠(yuǎn)不夠的，必須從課堂走向?qū)嵺`。而這次的課程設(shè)計(jì)，正好給了我們一個(gè)機(jī)會讓我們找出自身狀況與實(shí)際需要的差距，并在以后的學(xué)習(xí)期間及時(shí)補(bǔ)充相關(guān)知識，為求職與正式工作做好充分的知識、能力準(zhǔn)備，從而縮短從校園走向社會的心理轉(zhuǎn)型期。14《計(jì)算機(jī)算法設(shè)計(jì)與分析》課