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

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

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