摘要當今科技迅速發展，運用計算機解決實際問題變得異常重要。尤其是運用計算機實現算法設計具要重大意義。算法設計與分析，其實可以解釋為一種優化問題，一般是對可以利用計算機解決的離散型問題的優化。主要目的就是為了解決某一問題而提出的各種不同的解決方案，并且要針對具體問題做細致的空間與時間復雜度分析。本文是運用動態規劃法解決租用游艇問題和回溯法解決部落衛隊問題。利用C++編程實現算法。動態規劃算法是將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。首先找出最優解的性質，并刻畫其結構特征，然后遞歸的定義最優值（寫出動態規劃方程）并且以自底向上的方式計算出最優值，最后根據計算最優值時得到的信息，構造一個最優解。回溯法算法是確定了解空間的組織結構后，回溯法從開始節點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始節點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的或節點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前的擴展結點就成為死結點。換句話說，這個節點，這個結點不再是一個活結點。此時，應往回（回溯）移動至最近一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸的在解空間中搜索，直到找到所要求的解或解空間中以無活結點為止。即通過確定初始解和剪枝函數原則畫出狀態圖進行搜索產生全部可行解。關鍵字：動態規劃法、租用游艇問題、回溯法、部落衛隊問題、C++目錄TOC\o"1-5"\h\z一、 動態規劃法解決租用游艇問題 2\o"CurrentDocument"1.1問題重述 2\o"CurrentDocument"1.2問題分析 2\o"CurrentDocument"1.3算法原理與設計 21.3.1算法原理 21.3.2算法設計 3\o"CurrentDocument"1.4算法實現與結果 4\o"CurrentDocument"1.5結果描述 5\o"CurrentDocument"二、 回溯法解決部落衛隊問題 6\o"CurrentDocument"2.1問題重述 6\o"CurrentDocument"2.2問題分析 6\o"CurrentDocument"2.3算法原理及設計 62.3.1算法原理 62.3.2算法設計 7\o"CurrentDocument"2.4算法實現 8\o"CurrentDocument"2.5結果描述 10三、 總結 12\o"CurrentDocument"參考文獻 13動態規劃法解決租用游艇問題、動態規劃法解決租用游艇問題1.1問題重述長江游艇俱樂部在長江上設置了n個游艇出租站1,2,…,n。有可以游艇出租站用游艇并在下游的任何一個游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),匚-：i-匕試設計一個算法，計算游艇出租站1到出租站n所需的最少租金。對于給定的游艇出租站i到游艇出租站j之間的租金為r(i,j),1<=i<j<=n，編程計算從游艇出租站1到游艇出租站n所需的最少租金。由文件提供輸入數據。文件的第1行中有1個正整數n(n<=200)，表示有n個游艇出租站。接下來的n-1行是一個半矩陣r(i,j),1<=i<j<=n。程序運行結束時，將計算出的從游艇出租站1到游艇出租站n所需的最少租金輸出到文件中。輸入文件示例 輸出文件示例123 1251571.2問題分析將每個出租站看作一個點，站與站之間的關系可以用有向無環圖表示，同時站與站之間的租金為邊的權。此問題可轉化成求站1到站n的最短路徑問題。用動態規劃求解，遞推方程如下所示：定義f[i][j]為站點i到站點j的最少租金。 ，i<k<j,1<=i,j<=n.初始最優解為「I川國。1.3算法原理與設計1.3.1算法原理本文主要適用動態規劃法的思想求解，其基本思想時將原問題分解為若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。該方法主要應用于最優化問題，這類問題會有多種可能的解，每個解都有一個值，而動態規劃找出其中最優(最大或最)值的解。若存在若干個取最優值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動態規劃允許這些子問題不獨立，也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結果保存起來,避免每次碰到時都要重復計算。因此，動態規劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現大量的重復。動態規劃法的關鍵就在于，對于重復出現的子問題，只在第一次遇到時加以求解，并把答案保存起來,讓以后再遇到時直接引用，不必重新求解。設計動態規劃法一般包含以下4個步驟為：?找出最優解的性質，并刻畫其結構特征；?遞歸地定義最優值；?以自底向上的方法計算出最優解；?根據計算最優值得到的信息，構造最優解。1.3.2算法設計intmain(){intnum,i,j,k;for(k=2;k<num;k++){for(i=0;i<num-k;i++){intmark=i+k;for(j=i+1;j<mark;j++){if(list[i][j]+list[j][mark]<list[i][mark]){list[i][mark]=list[i][j]+list[j][mark];}}}}cout<<list[0][num-1];return0;}本課設中list[0][n-1]代表所用租金最少，n為游艇出租站的個數。List[i][j]表示從第i個游艇出租站到第j個游艇出租站的費用(其中i<j)。當list[i][j]+list[j][mark]<list[i][mark]時,list[i][mark]=list[i][j]+list[j][mark]。則遞歸方程為list[0][n-1]=min{list[0][k]+list[k][n-1],list[0][n-1]}1.4算法實現與結果程序代碼：#include<iostream>#include<vector>usingnamespacestd;intmain(){intnum,i,j,k,tmp;cin>>num;vector<vector<int>>list;vector<int>line;for(i=0;i<num-1;i++){list.push_back(line);for(j=0;j<=i;j++) //在容器前面添加些0，從而使list[i][j]表示從第i個出租站到第j個出租站所需的金額{ 〃同時也去除無效的表示，比如list[0][0]直接賦值為0，從而使后面的計算更方便list[i].push_back(0);}for(j=i+1;j<num;j++){cin>>tmp;list[i].push_back(tmp); 〃從i+1個出租站到第j+1個出租站所需金額}}for(k=2;k<num;k++) //從兩個出租站開始，逐步計算每幾個出租站之間的最優解，最終計算num-1個出租站合并的最優解for(i=0;i<num-k;i++){intmark=i+k;for(j=i+1;j<mark;j++){if(list[i][j]+list[j][mark]<list[i][mark])//例如list[0][1]+list[1][2]<list[0][2],則改變list[0][2]的值{list[i][mark]=list[i][j]+list[j][mark];}}}}cout<<list[0][num-1];return0;}1.5結果描述運行結果如圖1.1所示。應*C:\DocimentsandSettLngsVAdiinistratar\桌面'機房我件\Debug\Cppl-eg- |~|~|~Bl15712Fressanykeytocontinue圖1.1租用游艇問題運行結果如圖1所示，含有3個游艇出租站，從出租站1到出租站2,3分別需要租金為5,15，從出租站2到出租站3需要租金為7,則運用動態規劃法求解出從出租站1到出租站3所需最少租金為12。二、回溯法解決部落衛隊問題2.1問題重述原始部落byteland中的居民們為了爭奪有限的資源，經常發生沖突。幾乎每個居民都是他的仇敵。部落酋長為了組織一支保衛部落的隊伍，希望從部落的居民中選出最多的居民入伍，并保證隊伍中任何2個人都不是仇敵。2.2問題分析本問題為組織一支隊伍保衛部落，并且衛隊中任意2人不能有仇敵關系，因而，實際可考慮在居民中選擇一個最大獨立團體問題。構建一個樹狀圖G,居民為樹狀圖G的頂點，居民間的關系為樹狀圖的邊界線。“1”表示兩個居民間沒有仇敵關系，“0”表示兩個居民間有仇敵關系。這樣最大獨立團問題就成了圖G頂點集的子集的選取問題，可用子集樹表示問題的解空間。設當前考察結點位于解空間樹的第i層。先考慮頂點到要選入獨立團中的所有結點都要相連（即無仇敵關系）且任意兩個結點都仇敵關系，然后進入左子樹進行深度優先遍歷，在進入右子樹。2.3算法原理及設計2.3.1算法原理具有限界函數的深度優先的方式系統第搜索問題的解的算法稱為回溯法。它可以系統地搜索某一個問題的所有解或任一解。回溯法是一個既帶有系統性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問整理為word格式回溯法搜索解空間樹時，通常采用兩種策略避免無效搜索，提高回溯法的搜索效率。其一是用約束函數在擴展結點處剪去不滿足約束的子樹；其二是用限界函數剪去得不到最優解的子樹。這兩類函數統稱為剪枝函數。問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個(最優)解。運用回溯法解題通常包含以下3個步驟：針對所給問題，定義問題的解空間；確定易于搜索的解空間結構；以深度優先的方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。對于本題來說，回溯法操作步驟如下：針對所給問題，定義問題的解空間；確定易于搜索的解空間結構；以深度優先方式搜索解空間，并在搜索過程中利用剪枝函數剪去無效的搜索。無向圖G的最大團問題可以看作是圖G的頂點集V的子集選取問題。因此可以用子集樹表示問題的解空間。設當前擴展節點Z位于解空間樹的第i層。在進入左子樹前，必須確認從頂點i到已入選的頂點集中每一個頂點都有邊相連。在進入右子樹之前，必須確認還有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。用鄰接矩陣表示圖G，n為G的居民數，cn存儲當前衛隊數，bestn存儲最大衛隊人數。cn+n-i為進入右子樹的上界函數，當cn+n-i<bestn時，不能在右子樹中找到更大的衛隊團，利用剪枝函數可將Z的右結點剪去。2.3.2算法設計voidBacktrack(inti,inta[20][20]){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestn二cn;return;}intok=1;for(intj=1;j<i;j++)if(x[j]&&a[i][j]=0){ok=0;break;}if(ok){x[i]=1;cn++;Backtrack(i+1,a);x[i]=0;cn--;}if(cn+n-i>bestn){x[i]=0;Backtrack(i+1,a);}}}用回溯法解決部落衛隊問題時，以深度優先方式搜索整個解空間，用完全二叉樹表示解空間。剪枝條件為：當前衛隊人數+剩余居民人數<當前最優解；得出的解用一個n元向量V=(x1,x2，一.，xn)來表示。2.4算法實現程序代碼：#include<iostream.h>#include<stdlib.h>#include<stdio.h>classclique{friendmaxclique(inta[20][20],int[],int);private:voidBacktrack(inti,inta[20][20]);intn,*x, //當前解*bestx,//當前最優解cn,//當前衛隊人數bestn;//當前最大衛隊人數};voidclique::Backtrack(inti,inta[20][20]){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestn二cn;return;}intok=1;for(intj=1;j<i;j++)if(x[j]&&a[i][j]=0){ok=0;break;}if(ok){x[i]=1;cn++;Backtrack(i+1,a);x[i]=0;cn--;}if(cn+n-i>bestn){x[i]=0;Backtrack(i+1,a);}}intmaxclique(inta[20][20],intv[],intn){cliqueY;Y.x=newint[n+1];Y.n=n;Y.cn=0;Y.bestn=0;Y.bestx二v;Y.Backtrack(1,a);delete[]Y.x;returnY.bestn;}intmain(void){inti,j,k;intv[20];intn,edge;//頂點和邊數inta[20][20];cout<<"請輸入人數:";cin>>n;for(i=1;i<=n;i++)v[i]=0;for(i=1;i<=n;i++)for(j=i;j<=n;j++)a[i][j]=a[j][i]=1;cout<<"請輸入這"<<i-1<<"個人的所有敵對關系cin>>edge;for(i=1;i<=edge;i++){cin>>j>>k;a[j][k]=a[k][j]=0;}cout<<maxclique(a,v,n)<<endl;for(i=1;i<=n;i++)cout<<v[i]<<'';return0;system("pause");}2.5結果描述運行結果如圖2.1所示。?人的所有敵對關系MW?人的所有敵對關系MW1018301Pressanykeytocontinue圖2.1部落衛隊輸出結果如圖2所示，部落居民人數為7個，存在敵對關系分別為（1,2）,（1,4）,（2,3），（2,4），（2,5），（2,6），（3,5），（3,6），（4,5），（5,6）時，輸出最優解空間為（1,0,1,0,0,0,1），組織衛隊人數最大值為3。由此可畫出居民人數n=7時的解空間樹如圖2.2所示。i=1i=2i=3n=3i=4cn=1,bestn=0bestn=3cn17n=3182321X1cn=1,best=1,bestn=3cn=1,ben=3cn=19124202227X001323626cn=1,bestn=0cn=2,best/n=0n=314=0,bestn=00n=3cn+n-icn=0,best,besti=1i=2i=3n=3i=4cn=1,bestn=0bestn=3cn17n=3182321X1cn=1,best=1,bestn=3cn=1,ben=3cn=19124202227X001323626cn=1,bestn=0cn=2,best/n=0n=314=0,bestn=00n=3cn+n-icn=0,best,bestX Xcn=2,bestn=0cn=1,bestn=3cn=2,bestn=3cn=1,bestn=3i=5X1 0X10 1 0cn+n-iWbestncn=2,bestn=0cn=2cn=1,bestn=3cn=2,bestn=3Xbestn=3i=6X cn+n-iWbestnX