算法設(shè)計(jì)與分析試驗(yàn)4報(bào)告

1、湖南科技學(xué)院實(shí)驗(yàn)報(bào)告系部數(shù)學(xué)與計(jì)算科學(xué)專業(yè)信息與計(jì)算科學(xué)成績評定班級信計(jì)0902班學(xué)號200905002231姓名易丹課程名稱算法設(shè)計(jì)與分析實(shí)驗(yàn)時(shí)間2012.5.18實(shí)驗(yàn)編號實(shí)驗(yàn)四實(shí)驗(yàn)名稱回溯法5實(shí)驗(yàn)環(huán)境實(shí)驗(yàn)?zāi)康腄315、一臺電腦、Codeblocks10.051. 理解回溯法的深度優(yōu)先搜索策略。2. 掌握用回溯法解題的算法框架。3. 掌握回溯法的設(shè)計(jì)策略。實(shí)驗(yàn)內(nèi)容（算法、程序、步驟和方法輸入、輸出、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果分析）實(shí)驗(yàn)內(nèi)容:1. 排兵布陣問題某游戲中，不同的兵種處在不同的地形上其攻擊能力不一樣，現(xiàn)有n個(gè)不同兵種的角色1,2,.,n，需安排在某戰(zhàn)區(qū)n個(gè)點(diǎn)上，角色i在j點(diǎn)上的攻擊力為 Ai

2、j。試設(shè)計(jì)一個(gè)布陣方案，使總的攻擊力最大。數(shù)據(jù)：防衛(wèi)點(diǎn)604080506090608070203050405080904030709060809060501234123452. 0-1背包問題（選做）編程實(shí)現(xiàn)0-1背包問題的回溯算法。 數(shù)據(jù)文件見附件。實(shí)驗(yàn)要求:1. 實(shí)驗(yàn)報(bào)告只寫實(shí)驗(yàn)。2. 寫出算法思想、主要程序代碼、算法復(fù)雜性分析。實(shí)驗(yàn)（1）的步驟、算法及運(yùn)行結(jié)果:1.回溯法的總體思想回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方 法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹

3、的 任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐 層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。2. 回溯法的實(shí)現(xiàn)。打開Codeblocks10.05，編輯頭文件Queue.h和主程序main.cpp,利用參考程序，同時(shí)還設(shè)計(jì)了從文件讀入 數(shù)據(jù)，使程序更清晰，其主要程序如下：Mai n.c pp#in elude <iostream> #in elude <sstream> #i nclude <fstream> #in elude <cstdlib> #defi ne INT_MA

4、X 90 using n ames pace std;temp late<ty pen ame Type/交換兩個(gè)變量的值 void Swap(Type &a,T ype &b)Type t=b; b=a;a=t;temp late<ty pen ame Typ e> / 創(chuàng)建二維數(shù)組 void TwoDimArray(T yp e* &p ,i nt r,i nt c)p=new Type *r; for(i nt i=0; i<r; i+) p i=new Typ ec;for(i nt i=0; i<r; i+)for(i nt j=

5、0; j<c; j+) pij=0;temp late<ty pen ame Type/ 輸出一維數(shù)組的元素 void Prin t1(T ype a,i nt n)for(i nt i=1; i<=n; i+)cout<<ai<<''cout<<e ndl;temp late<t ypen ame T>void Inp utData2(T *M,i nt r,int c,char *file name)ifstream in file;in file. open( file name);/ 打開文件if(!i

6、nfile)/測試是否已經(jīng)成功地打開了文件cerr<<"文件打開失??！"<<e ndl;exit(1);結(jié)束程序stri ng s;for(i nt i=0; i<r; +i) / 讀取矩陣數(shù)據(jù)getline(infile,s); / 讀一行istringstream ss(s); /創(chuàng)建字符串流 ssfor(i nt j=0; j<c; +j)ss>>Mij;/從流中讀取一個(gè)T類型的數(shù)賦給Mclass Flowsho pfrie nd int Flow(i nt *,i nt,i nt );p rivate:void Bac

7、ktrack(i nt i);int *M;/各作業(yè)所需的處理時(shí)間int *x; /當(dāng)前位置安排int *bestx; 當(dāng)前最優(yōu)攻擊力int *f2;機(jī)器2完成處理時(shí)間int f1;/機(jī)器1完成處理時(shí)間int f;/當(dāng)前攻擊力int bestf; /當(dāng)前最優(yōu)值int n;角色;void Flowsh op:Backtrack。nt i)if(i> n)int t=0;for(i nt i=1; i<=n; i+) t+=M xii;if(t>bestf)bestf=t;for(i nt j=1;j<=n ;j+) bestxj=xj;elsefor(int j=i; j

8、<=n; j+)/自 i 后，有i:n項(xiàng)作業(yè)Swap(xi,xj); /xj成為第 i 個(gè)作業(yè) Backtrack(i+1);Swa p(xi,xj);int Flow(i nt *M,i nt n,i nt bestx)Flowshop X;/初始X對象的數(shù)據(jù)X.x=new in t n+1;X.f2=new in t n+1;X.M=M;X. n=n;X.bestx=bestx;X.bestf=0;X.f1=0;X.f=0;for(i nt i=0; i<=n; i+)X.f2i=0;X.xi=i;X.Backtrack(1); delete X.x;delete X.f2;r

9、eturn X.bestf;int mai n()Flowsho p X;int *M;int n;int *bestx;int bestf;TwoDimArray(M,5,5);X.x=new in t n+1;X.M=M;X. n=n;X.bestx =new intn+1;X.bestf=0;int s=Flow(M, n,bestf); cout<<s<<e ndl;Prin t1(bestx,5); return 0;運(yùn)行結(jié)果:0 C;cuKent s and?e3070 be4ea2 540504080seQB403090se7B5670ee26se905Qi"et：urne(l 0ProcessKpgss any key to continue-execut ion t ine : 0_233 s今天主要學(xué)的是回溯法，由于上一次實(shí)驗(yàn)老師要求我們從文件輸入數(shù)據(jù)，因此這一 次我同樣利用了該種方式，將矩陣中的數(shù)據(jù)仍從文件輸入，還挺好上手的，但是本該順 暢的實(shí)驗(yàn)過程中卻出現(xiàn)了一個(gè)笨錯(cuò)誤，就是我的程序調(diào)試總是不正確，我還想著明明就 和別人的差不多，不應(yīng)該啊-但是別的同學(xué)都可以