1、精選優(yōu)質(zhì)文檔-傾情為你奉上用分治法解決快速排序問題及用動態(tài)規(guī)劃法解決最優(yōu)二叉搜索樹問題及用回溯法解決圖的著色問題一、 課程設計目的：計算機算法設計與分析這門課程是一門實踐性非常強的課程，要求我們能夠?qū)⑺鶎W的算法應用到實際中，靈活解決實際問題。通過這次課程設計，能夠培養(yǎng)我們獨立思考、綜合分析與動手的能力，并能加深對課堂所學理論和概念的理解，可以訓練我們算法設計的思維和培養(yǎng)算法的分析能力。二、課程設計內(nèi)容：1、分治法：（2）快速排序；2、動態(tài)規(guī)劃：（4）最優(yōu)二叉搜索樹；3、回溯法：（2）圖的著色。三、概要設計：l 分治法快速排序：分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這

2、些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。分治法的條件：（1) 該問題的規(guī)模縮小到一定的程度就可以容易地解決；（2) 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；（3) 利用該問題分解出的子問題的解可以合并為該問題的解；（4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。 抽象的講，分治法有兩個重要步驟：（1）將問題拆開；（2）將答案合并；l 動態(tài)規(guī)劃最優(yōu)二叉搜索樹： 動態(tài)規(guī)劃的基本思想是將問題分解為若干個小問題，解子問題，然后從子問題得到原問題的解。設計動態(tài)規(guī)劃法的步驟： （1） 找出最

3、優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（2）遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；（3）以自底向上的方式計算出最優(yōu)值；（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。l 回溯法圖的著色回溯法的基本思想是確定了解空間的組織結(jié)構(gòu)后，回溯法就是從開始節(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始節(jié)點就成為一個活結(jié)點，同時也成為當前的擴展結(jié)點。在當前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的或節(jié)點，并成為當前擴展結(jié)點。如果在當前的擴展結(jié)點處不能再向縱深方向移動，則當前的擴展結(jié)點就成為死結(jié)點。換句話說，這個節(jié)點，這個結(jié)點不再是一個活結(jié)點。此時，應往回（回溯）移動至最近一

4、個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點。回溯法即以這種工作方式遞歸的在解空間中搜索，直到找到所要求的解或解空間中以無活結(jié)點為止。四、詳細設計與實現(xiàn)：l 分治法快速排序快速排序是基于分治策略的另一個排序算法。其基本思想是，對于輸入的子數(shù)組,按以下三個步驟進行排序： （1）、分解(divide) 以元素為基準元素將劃分為三段，和，使得中任何一個元素都小于，而中任何一個元素大于等于，下標在劃分過程中確定。（2）、遞歸求解(conquer) 通過遞歸調(diào)用快速排序算法分別對和進行排序。（3）、合并(merge) 由于和的排序都是在原位置進行的，所以不必進行任何合并操作就已經(jīng)排好序了。算法實現(xiàn)題:

5、現(xiàn)將數(shù)列23 21 34 45 65 76 86 46 30 39 89 20 2 3 8 47 38 54 59 40進行快速排序。源程序如下：#include <iostream>using namespace std;#define size 20 int partition(int data,int p,int r) int n=datap,i=p+1,j=r,temp; /將<n的元素交換到左邊區(qū)域 /將>n的元素交換到右邊區(qū)域 while(true) while(datai<n) +i; while(dataj>n) -j; if(i>=j

6、) break; temp=datai; datai=dataj; dataj=temp; datap=dataj; dataj=n; return j; void quick_sort(int data,int p,int r) if(p>=r) return; int q=partition(data,p,r); quick_sort(data,p,q-1); /對左半段排序 quick_sort(data,q+1,r); /對右半段排序 int main() int i,n,datasize;printf("請輸入要排列的數(shù)目（<=20）：");scanf

7、("%d",&n);printf("請輸入要排列的數(shù)列：n"); for(i=0;i<n;+i) scanf("%d",&datai); quick_sort(data,0,n-1);printf("排列后的數(shù)列為：n"); for(i=0;i<n;+i) printf( "%d ",datai); printf("n");return 0; 運行結(jié)果如下：圖1l 動態(tài)規(guī)劃最優(yōu)二叉搜索樹1、最優(yōu)二叉搜索樹問題描述和分析：設是有序集，且，表示有序集S

8、的二叉搜索樹利用二叉樹的結(jié)點存儲有序集中的元素。它具有下述性質(zhì)：存儲于每個結(jié)點中的元素x大于其左子樹中任一結(jié)點所存儲的元素，小于其右子樹中任一結(jié)點所存儲的元素。二叉樹的葉結(jié)點是形如的開區(qū)間，在表示S的二叉搜索樹中搜索元素x，返回的結(jié)果有兩種情況：（1）在二叉搜索樹的內(nèi)結(jié)點中找到。（2）在二叉搜索樹的葉結(jié)點中確定。設在第(1)中情形中找到元素的概率為；在第(2)種情形中確定的概率為。其中約定。顯然有：稱為集合S的存取概率分布。在表示S的二叉搜索樹T中，設存儲元素的結(jié)點深度為；葉結(jié)點的結(jié)點深度為，則：表示在二叉搜索樹T中進行一次搜索所需要的平均比較次數(shù)，p又成為二叉搜索樹T的平均路長。在一般情況下

9、，不同的二叉搜索樹的平均路長是不相同的。最優(yōu)二叉搜索樹問題是對于有序集S及其存取概率分布，在所有表示有序集S的二叉搜索樹中找到一棵具有最小平均路長的二叉搜索樹。2、最優(yōu)子結(jié)構(gòu)性質(zhì)：二叉搜索樹T的一棵含有結(jié)點和葉結(jié)點的子樹可以看作是有序集關(guān)于全集合的一棵二叉搜索樹，其存取概率為以下的條件概率：式中，。 設是有序集關(guān)于存取概率的一棵最優(yōu)二叉搜索樹，其平均路長為。的根結(jié)點存儲元素。其左右子樹和的平均路長分別為和。由于和中結(jié)點深度是它們在中的結(jié)點深度減1，故有：由于是關(guān)于集合的一棵二叉搜索樹，故。若，則用替換可得到平均路長比更小的二叉搜索樹。這與是最優(yōu)二叉搜索樹矛盾。故是一棵最優(yōu)二叉搜索樹。同理可證也

10、是一棵最優(yōu)二叉搜索樹。因此最優(yōu)二叉搜索樹問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3、遞歸計算最優(yōu)值：最優(yōu)二叉搜索樹的平均路長為，則所求的最優(yōu)值為。由最優(yōu)二叉搜索樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可建立計算的遞歸式如下：初始時，。記為，則為所求的最優(yōu)值。計算的遞歸式為：據(jù)此，可設計出解最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法。 算法實現(xiàn)題: 給出標識符集1,2,3=do,if,stop存取概率，若b1=0.4 b2=0.2 b3=0.05 a0=0.2 a1=0.05 a2=0.05 a3=0.05構(gòu)造一棵最優(yōu)二叉搜索樹源程序如下：#include<iostream>using namespace std;void O

11、ptimalBinarySearchTree(float a,float b,int n,float m20,int s20,float w20) /求解最優(yōu)值的方法int i,r,k; float t; for(i=0;i<=n;i+) wi+1i=ai; /搜索不到的點,最優(yōu)解為0 mi+1i=0; for(r=0;r<n;r+) for(i=1;i<=n-r;i+) int j=i+r; /左子樹為空 wij=wij-1+aj+bj; mij=mi+1j; sij=i; for(k=i+1;k<=j;k+) t=mik-1+mk+1j; if(t<mij)

12、/以k為根節(jié)點，左子樹不為空 mij=t; sij=k; mij+=wij; for(i=1;i<=n;i+) for(int j=1;j<=n;j+) cout<<"s"<<i<<""<<j<<"="<<sij<<endl;void print(int i,int j,int s20,int S) /遞歸輸出結(jié)果 if(j>=i) int k=sij;cout<<"(" print(i,k-1,s,S

13、); cout<<")" cout<<" "<<Sk<<" " cout<<"(" print(k+1,j,s,S); cout<<")" int main() /主函數(shù)int n,i; float a20,b20,m2020,w2020; int s2020,S20; cout<<"請輸入有序集元素的個數(shù)n："<<endl; cin>>n; cout<<&

14、quot;請輸入有序集各元素的值Si(一共"<<n<<"個):"<<endl; for(i=1;i<=n;i+) cin>>Si; cout<<"請輸入概率數(shù)組a的各元素的值ai(一共"<<n+1<<"個):"<<endl; for(i=0;i<=n;i+) cin>>ai; cout<<"請輸入概率數(shù)組b的各元素的值bi(一共"<<n<<"

15、個):"<<endl; for(i=1;i<=n;i+) cin>>bi; OptimalBinarySearchTree(a,b,n,m,s,w); cout<<"最優(yōu)值即平均步長為："<<m1n<<endl;運行結(jié)果如下：圖2l 回溯法圖的著色 1、圖的m著色問題描述：給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色

16、，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。2、算法設計：一般連通圖的可著色法問題并不僅限于平面圖。給定圖和m種顏色，如果這個圖不是m可著色，則給出否定答案；如果這個圖是m可著色的，找出所有不同的著色方法下面根據(jù)回朔法的遞歸描述框架設計圖的m著色算法。用圖的鄰接矩陣a表示無向量連通圖。若屬于圖的邊集E，則，否則。整數(shù)1，2，m用來表示m種不同顏色。頂點所有顏色用表示，數(shù)組是問題的解向量。問題的解空間可表示為一棵高度為n+1的完全m叉樹。解空間樹的第層中每一結(jié)點都有m個兒子，每個兒子相應于的m個可能的著色之一。 第n+1層結(jié)點均為葉結(jié)點。 在下面的解圖的m可著色問

17、題的回溯法中，搜索解空間中第層子樹。類的數(shù)據(jù)成員記錄解空間中結(jié)點信息，以減少傳給的參數(shù)。記錄當前已找到的m著色方案數(shù)。在算法中，當時，算法搜索至葉結(jié)點，得到新的m著色方案，當前找到的m著色方案數(shù)則增1。而當時,當前擴展結(jié)點Z的每一個解空間中內(nèi)部結(jié)點.該結(jié)點有共m個兒子結(jié)點.對當前擴展結(jié)點Z的每一兒子結(jié)點,有方法ok檢查其可行性,并以深度優(yōu)先的方式遞歸的對可行子樹搜索,或減去不可行樹。 算法實現(xiàn)題: 給定如圖3所示的一個無向連通圖G，現(xiàn)有4種不同的顏色，用這4種顏色為圖G的各頂點著色，每個頂點著一種顏色。要求：G中每條邊的2個頂點著有不同的顏色。問一共有多少種著色方案？12354圖3源程序如下：

18、#include <iostream>using namespace std;int n; /圖的頂點個數(shù)int m; /可用顏色數(shù)int i,j; int a1010; /程序中使用時從下標1開始;程序中用于存儲圖的鄰接矩陣int x10; /用于存儲當前解long sum; /當前已找到的可著色方案數(shù)bool Ok(int k)for(int j=1;j<=n;j+)if(akj=1)&&(xj=xk) /akj=1表示的是第k點和第j點是相連的return false; return true;void Backtrack(int t)if(t>n

19、) /t是表示的第t行葉結(jié)點；圖的m著色共有n個結(jié)點 sum+;cout<<" 第"<<sum<<"種解決方案為 ：n"for(int i=1;i<=n;i+)cout<<xi<<" " cout<<endl; elsefor(int i=1;i<=m;i+)xt=i;if(Ok(t)Backtrack(t+1); /判斷t+1結(jié)點的顏色是不是正確xt=0; /把t+1結(jié)點的顏色換一種long mColoring(int mm) m=mm; sum=0; Backtrack(1); return sum;void main()cout<<"nt=圖的m著色問題=n"cout<<"輸入圖的頂點數(shù)與可用的顏色數(shù) :n"cin>>n>>m;cout<<"n=輸入圖的鄰接矩陣n"for(i=1;i<=n;i