算法課程設(shè)計(jì)

1、摘要當(dāng)今科技迅速發(fā)展，運(yùn)用計(jì)算機(jī)解決實(shí)際問題變得異常重要。尤其是運(yùn)用計(jì)算機(jī)實(shí)現(xiàn)算法設(shè)計(jì)具要重大意義。算法設(shè)計(jì)與分析，其實(shí)可以解釋為一種優(yōu)化問題，一般是對(duì)可以利用計(jì)算機(jī)解決的離散型問題的優(yōu)化。主要目的就是為了解決某一問題而提出的各種不同的解決方案，并且要針對(duì)具體問題做細(xì)致的空間與時(shí)間復(fù)雜度分析。本文是運(yùn)用動(dòng)態(tài)規(guī)劃法解決租用游艇問題和回溯法解決部落衛(wèi)隊(duì)問題。利用C+編程實(shí)現(xiàn)算法。動(dòng)態(tài)規(guī)劃算法是將待求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。首先找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征，然后遞歸的定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）并且以自底向上的方式計(jì)算出最優(yōu)值，最后根據(jù)計(jì)

2、算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。回溯法算法是確定了解空間的組織結(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)。換句話說，這個(gè)節(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回（回溯）移動(dòng)至最近一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸的在解空間中搜索，直到找到所要求的解或解空間中以無活結(jié)點(diǎn)為止。即通過確定初始解

3、和剪枝函數(shù)原則畫出狀態(tài)圖進(jìn)行搜索產(chǎn)生全部可行解。關(guān)鍵字：動(dòng)態(tài)規(guī)劃法、租用游艇問題、回溯法、部落衛(wèi)隊(duì)問題、C+目 錄一、 動(dòng)態(tài)規(guī)劃法解決租用游艇問題21.1問題重述21.2 問題分析21.3 算法原理與設(shè)計(jì)21.3.1 算法原理21.3.2 算法設(shè)計(jì)31.4 算法實(shí)現(xiàn)與結(jié)果41.5結(jié)果描述5二、回溯法解決部落衛(wèi)隊(duì)問題62.1問題重述62.2問題分析62.3算法原理及設(shè)計(jì)62.3.1算法原理62.3.2算法設(shè)計(jì)72.4算法實(shí)現(xiàn)82.5結(jié)果描述10三、總結(jié)12參考文獻(xiàn)13一、 動(dòng)態(tài)規(guī)劃法解決租用游艇問題 1.1問題重述長(zhǎng)江游艇俱樂部在長(zhǎng)江上設(shè)置了n個(gè)游艇出租站1,2,n。有可以游艇出租站用游艇并在下

4、游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),1=ij=n。試設(shè)計(jì)一個(gè)算法，計(jì)算游艇出租站1到出租站n所需的最少租金。對(duì)于給定的游艇出租站i 到游艇出租站j 之間的租金為r(i,j),1=ij=n，編程計(jì)算從游艇出租站1 到游艇出租站n所需的最少租金。 由文件提供輸入數(shù)據(jù)。文件的第1 行中有1 個(gè)正整數(shù)n（n=200），表示有n個(gè)游艇出租站。接下來的n-1 行是一個(gè)半矩陣r(i,j),1=ij=n。程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的從游艇出租站1 到游艇出租站n所需的最少租金輸出到文件中。 輸入文件示例 輸出文件示例 123 125 15 71.2 問題分析 將每

5、個(gè)出租站看作一個(gè)點(diǎn)，站與站之間的關(guān)系可以用有向無環(huán)圖表示，同時(shí)站與站之間的租金為邊的權(quán)。此問題可轉(zhuǎn)化成求站1到站n的最短路徑問題。用動(dòng)態(tài)規(guī)劃求解，遞推方程如下所示：定義fij為站點(diǎn)i到站點(diǎn)j的最少租金。fij=minfik+fkj,ikj,1=i,j=n.初始最優(yōu)解為f1n。1.3 算法原理與設(shè)計(jì)1.3.1 算法原理本文主要適用動(dòng)態(tài)規(guī)劃法的思想求解，其基本思想時(shí)將原問題分解為若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)(最大或最)值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一

6、個(gè)。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問題不獨(dú)立，也允許其通過自身子問題的解作出選擇，該方法對(duì)每一個(gè)子問題只解一次，并將結(jié)果保存起來，避免每次碰到時(shí)都要重復(fù)計(jì)算。因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問題樹 中的子問題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不必重新求解。設(shè)計(jì)動(dòng)態(tài)規(guī)劃法一般包含以下4個(gè)步驟為：u 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；u 遞歸地定義最優(yōu)值；u 以自底向上的方法計(jì)算出最優(yōu)解；u 根據(jù)

7、計(jì)算最優(yōu)值得到的信息，構(gòu)造最優(yōu)解。1.3.2 算法設(shè)計(jì) int main() int num,i,j,k; for(k=2;knum;k+) for(i=0;inum-k;i+)int mark=i+k; for(j=i+1;jmark;j+) if(listij+listjmarklistimark) listimark=listij+listjmark; coutlist0num-1;return 0;本課設(shè)中l(wèi)ist0n-1代表所用租金最少，n為游艇出租站的個(gè)數(shù)。Listij表示從第i個(gè)游艇出租站到第j個(gè)游艇出租站的費(fèi)用（其中ij）。當(dāng)listij+listjmarklistimark時(shí)

8、，listimark= listij +listjmark。則遞歸方程為list0n-1=minlist0k+listkn-1,list0n-11.4 算法實(shí)現(xiàn)與結(jié)果程序代碼：#include #include using namespace std;int main() int num,i,j,k,tmp; cinnum; vector vector list; vectorline; for(i=0;inum-1;i+) list.push_back(line); for(j=0;j=i;j+) /在容器前面添加些0，從而使listij表示從第i個(gè)出租站到第j個(gè)出租站所需的金額 /同時(shí)也去

9、除無效的表示，比如list00直接賦值為0，從而使后面的計(jì)算更方便 listi.push_back(0); for(j=i+1;jtmp; listi.push_back(tmp); /從i+1個(gè)出租站到第j+1個(gè)出租站所需金額 for(k=2;knum;k+) /從兩個(gè)出租站開始，逐步計(jì)算每幾個(gè)出租站之間的最優(yōu)解，最終計(jì)算num-1個(gè)出租站合并的最優(yōu)解 for(i=0;inum-k;i+) int mark=i+k; for(j=i+1;jmark;j+) if(listij+listjmarklistimark) /例如list01+list12list02,則改變list02的值 lis

10、timark=listij+listjmark; coutlist0num-1; return 0;1.5結(jié)果描述運(yùn)行結(jié)果如圖1.1所示。圖1.1 租用游艇問題運(yùn)行結(jié)果如圖1所示，含有3個(gè)游艇出租站，從出租站1到出租站2，3分別需要租金為5，15，從出租站2到出租站3需要租金為7，則運(yùn)用動(dòng)態(tài)規(guī)劃法求解出從出租站1到出租站3所需最少租金為12。二、回溯法解決部落衛(wèi)隊(duì)問題2.1問題重述原始部落byteland中的居民們?yōu)榱藸?zhēng)奪有限的資源，經(jīng)常發(fā)生沖突。幾乎每個(gè)居民都是他的仇敵。部落酋長(zhǎng)為了組織一支保衛(wèi)部落的隊(duì)伍，希望從部落的居民中選出最多的居民入伍，并保證隊(duì)伍中任何2個(gè)人都不是仇敵。2.2問題分析

11、 本問題為組織一支隊(duì)伍保衛(wèi)部落，并且衛(wèi)隊(duì)中任意2人不能有仇敵關(guān)系，因而，實(shí)際可考慮在居民中選擇一個(gè)最大獨(dú)立團(tuán)體問題。 構(gòu)建一個(gè)樹狀圖G,居民為樹狀圖G的頂點(diǎn)，居民間的關(guān)系為樹狀圖的邊界線?！?”表示兩個(gè)居民間沒有仇敵關(guān)系，“0”表示兩個(gè)居民間有仇敵關(guān)系。這樣最大獨(dú)立團(tuán)問題就成了圖G頂點(diǎn)集的子集的選取問題，可用子集樹表示問題的解空間。設(shè)當(dāng)前考察結(jié)點(diǎn)位于解空間樹的第i層。先考慮頂點(diǎn)到要選入獨(dú)立團(tuán)中的所有結(jié)點(diǎn)都要相連（即無仇敵關(guān)系）且任意兩個(gè)結(jié)點(diǎn)都仇敵關(guān)系，然后進(jìn)入左子樹進(jìn)行深度優(yōu)先遍歷，在進(jìn)入右子樹。2.3算法原理及設(shè)計(jì)2.3.1算法原理 具有限界函數(shù)的深度優(yōu)先的方式系統(tǒng)第搜索問題的解的算法稱為回

12、溯法。它可以系統(tǒng)地搜索某一個(gè)問題的所有解或任一解。回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。它適用于解一些組合數(shù)較大的問題。 回溯法搜索解空間樹時(shí)，通常采用兩種策略避免無效

13、搜索，提高回溯法的搜索效率。其一是用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；其二是用限界函數(shù)剪去得不到最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)。 問題的解空間：應(yīng)用回溯法解問題時(shí)，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)到少包含問題的一個(gè)（最優(yōu)）解。 運(yùn)用回溯法解題通常包含以下3個(gè)步驟：（1）針對(duì)所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。對(duì)于本題來說，回溯法操作步驟如下：(1)針對(duì)所給問題，定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)；以深度優(yōu)先方式搜索解空間，并在搜索過程中利用剪枝函數(shù)剪去無效的搜索。(

14、2)無向圖G的最大團(tuán)問題可以看作是圖G的頂點(diǎn)集V的子集選取問題。因此可以用子集樹表示問題的解空間。設(shè)當(dāng)前擴(kuò)展節(jié)點(diǎn)Z位于解空間樹的第i層。在進(jìn)入左子樹前，必須確認(rèn)從頂點(diǎn)i到已入選的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。在進(jìn)入右子樹之前，必須確認(rèn)還有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。(3)用鄰接矩陣表示圖G，n為G的居民數(shù)，cn存儲(chǔ)當(dāng)前衛(wèi)隊(duì)數(shù)，bestn存儲(chǔ)最大衛(wèi)隊(duì)人數(shù)。cn+n-i為進(jìn)入右子樹的上界函數(shù)，當(dāng)cn+n-in)for(int j=1;j=n;j+) bestxj=xj;bestn=cn;return;int ok=1;for(int j=1;jbestn)xi=0;Ba

15、cktrack(i+1,a);用回溯法解決部落衛(wèi)隊(duì)問題時(shí)，以深度優(yōu)先方式搜索整個(gè)解空間，用完全二叉樹表示解空間。剪枝條件為：當(dāng)前衛(wèi)隊(duì)人數(shù)+剩余居民人數(shù)當(dāng)前最優(yōu)解；得出的解用一個(gè)n元向量V=（x1,x2,.,xn）來表示。2.4算法實(shí)現(xiàn)程序代碼：#include #include #include class cliquefriend maxclique(int a2020,int ,int);private:void Backtrack(int i,int a2020);int n,*x, /當(dāng)前解*bestx, /當(dāng)前最優(yōu)解cn , /當(dāng)前衛(wèi)隊(duì)人數(shù)bestn; /當(dāng)前最大衛(wèi)隊(duì)人數(shù);void

16、clique:Backtrack(int i,int a2020)if(in)for(int j=1;j=n;j+) bestxj=xj;bestn=cn;return;int ok=1;for(int j=1;jbestn)xi=0;Backtrack(i+1,a);int maxclique(int a2020,int v,int n)clique Y;Y.x=new intn+1;Y.n=n;Y.cn=0;Y.bestn=0;Y.bestx=v;Y.Backtrack(1,a);delete Y.x;return Y.bestn;int main(void) int i,j,k;int

17、v20;int n,edge; /頂點(diǎn)和邊數(shù)int a2020;coutn;for(i=1;i=n;i+)vi=0;for(i=1;i=n;i+)for(j=i;j=n;j+)aij=aji=1;cout請(qǐng)輸入這i-1edge;for(i=1;ijk;ajk=akj=0;coutmaxclique(a,v,n)endl;for(i=1;i=n;i+)coutvi ;return 0; system(pause);2.5結(jié)果描述運(yùn)行結(jié)果如圖2.1所示。圖2.1 部落衛(wèi)隊(duì)輸出結(jié)果 如圖2所示，部落居民人數(shù)為7個(gè)，存在敵對(duì)關(guān)系分別為（1,2），（1,4），（2，3），（2,4），（2，5），（2,6

18、），（3,5），（3,6），（4,5），（5,6）時(shí)，輸出最優(yōu)解空間為（1,0,1,0,0,0,1），組織衛(wèi)隊(duì)人數(shù)最大值為3。由此可畫出居民人數(shù)n=7時(shí)的解空間樹如圖2.2所示。0123456789101112131415161718192021222324252627i=1 cn=0,best n=010cn=1,best n=0cn=0,best n=3i=21010 cn=1,best n=0cn=1,best n=3 cn=0,best n=3i=3 101 01 0cn=2,best n=0 cn=1,best n=3cn=1,best n=3 cn=1,best n=3 cn=0,

19、best n=3i=4 101 0 cn+n-ibest n 1 0cn+n-ibest n cn=2,best n=0 cn=1,best n=3cn=2,best n=3 cn=1,best n=3i=5 1 0 1 01 0 cn+n-ibest n cn=2,best n=0 cn=2cn=1,best n=3cn=2,best n=3 best n=3i=6 cn+n-ibest n cn+n-ibest n 1 0 cn=2,best n=0i=7 1 cn=3,best n=0i=8 best n=3圖2.2 解空間樹三、總結(jié) 我通過一學(xué)期對(duì)算法分析與設(shè)計(jì)的初步學(xué)習(xí)，了解了一些算法的思想，并運(yùn)用到本次算法課程設(shè)計(jì)中。通過本次課程設(shè)計(jì)，使我對(duì)動(dòng)態(tài)規(guī)劃法解決租用游艇