算法實驗報告14700字

算法實驗報告14700字

中南大學(xué)算法設(shè)計與分析實驗報告學(xué)生姓名惠苗壯指導(dǎo)教師鄭瑾專業(yè)班級計科0904班學(xué)號0909091627完成時間20xx年12月18日學(xué)院信息科學(xué)與工程學(xué)院目錄一．實驗?zāi)康???????????????1二．實驗要求???????????????1三．實驗內(nèi)容???????????????1四．實驗分析???????????????1五．實驗結(jié)果???????????????15六．實驗心得???????????????20一．實驗?zāi)康模?.掌握動態(tài)規(guī)劃、回溯法、分支限定法的原理。2.能獨立完成上述算法的實現(xiàn)。3.能用上述算法解決問題。二．實驗要求：1.給出相應(yīng)的測試結(jié)果。2.給出源代碼及相應(yīng)的注釋。3.所有的輸入和輸出都用文件處理。三．實驗內(nèi)容：1.實現(xiàn)求n皇后問題和子集和數(shù)問題的回溯算法。2.用動態(tài)規(guī)劃的方法實現(xiàn)0/1背包問題。3.用分支限界法實現(xiàn)0/1背包問題。4.用深度優(yōu)化的方法遍歷一個圖，并判斷圖中是否有回路存在，如果有，請輸出回路。四．實驗分析：實驗一：實現(xiàn)求n皇后問題和子集和數(shù)問題的回溯算法。問題說明：按照國際象棋的規(guī)則在N*N的棋盤上放置彼此不受攻擊的皇后問題。數(shù)據(jù)表示：用n個數(shù)彼此用“，”隔開來表示那個皇后的最后位置，如：4皇后問題中，最后結(jié)果為1,3,0,2，表示第0列的皇后的位置在1，第1列的皇后的位置在3，第2列皇后的位置在0，第4列的皇后的位置在2.n皇后以此類推。代碼如下:#include"stdio.h"#include"stdlib.h"#include"math.h"intx[4]={0};intPlace(intk)//判斷第k行當(dāng)前列是否可以放置皇后{for(inti=0;i<k;i++){}voidNQueens(intk){x[k]=-1;}return1;if(x[i]==x[k]||(abs(x[i]-x[k])-abs(i-k))==0){}return0;while(1){x[k]=x[k]+1;while((x[k]<4)&&(!Place(k)))x[k]=x[k]+1;if(x[k]<4){if(k<3)NQueens(k+1);else{for(inti=0;i<4;i++){}}printf("%d,",x[i]);}printf("\n");elsereturn;}}intmain(intargc,char*argv[]){}NQueens(0);system("PAUSE");實驗二：用動態(tài)規(guī)劃的方法實現(xiàn)0/1背包問題。問題說明：給定n種物品和一背包。物品i的重量是w，其價值是v，背包的容量為C。求應(yīng)怎樣裝入物體使得裝入背包中的物體總價值最大。算法說明:采用動態(tài)規(guī)劃的方法，將待求解問題分解成若干個子問題，然后從這些子問題的解得到原問題的解。在該問題中需要決定x1..xn的值。假設(shè)按i=1，2，...，n的次序來確定xi的值。如果置x1=0，則問題轉(zhuǎn)變?yōu)橄鄬τ谄溆辔锲?即物品2，3，.，n)，背包容量仍為c的背包問題。若置x1=1，問題就變?yōu)殛P(guān)于最大背包容量為c-w1的問題。現(xiàn)設(shè)r?{c，c-w1}為剩余的背包容量。在第一次決策之后，剩下的問題便是考慮背包容量為r時的決策。不管x1是0或是1，[x2，.，xn]必須是第一次決策之后的一個最優(yōu)方案，如果不是，則會有一個更好的方案[y2，.，yn]，因而[x1，y2，.，yn]是一個更好的方案。假設(shè)n=3,w=[100,14,10],p=[20,18,15],c=116。若設(shè)x1=1，則在本次決策之后，可用的背包容量為r=116-100=16。[x2，x3]=[0,1]符合容量限制的條件，所得值為15，但因為[x2，x3]=[1，0]同樣符合容量條件且所得值為18，因此[x2，x3]=[0，1]并非最優(yōu)策略。即x=[1，0，1]可改進為x=[1，1，0]。若設(shè)x1=0，則對于剩下的兩種物品而言，容量限制條件為116?？傊?，如果子問題的結(jié)果[x2，x3]不是剩余情況下的一個最優(yōu)解，則[x1，x2，x3]也不會是總體的最優(yōu)解。在此問題中，最優(yōu)決策序列由最優(yōu)決策子序列組成。假設(shè)f(i,y)表示剩余容量為y，剩余物品為i，i+1，...，n時的最優(yōu)解的值，即：利用最優(yōu)序列由最優(yōu)子序列構(gòu)成的結(jié)論，可得到f的遞歸式為：當(dāng)j>=wi時：f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi}①式當(dāng)0<=j時：fn(1,c)是初始時背包問題的最優(yōu)解。以本題為例：若0≤y＜10，則f(3,y)=0；若y≥10，f(3,y)=15。利用②式，可得f(2,y)=0(0≤y＜10)；f(2，y)=15(10≤y＜14)；f(2，y)=18(14≤y＜24)和f(2，y)=33(y≥24)。因此最優(yōu)解f(1,116)=max{f(2，116)，f(2，116-w1)+p1}=max{f(2，116)，f(2，16)+20}=max{33，38}=38?，F(xiàn)在計算xi值，步驟如下：若f(1,c)=f(2,c)，則x1=0，否則x1=1。接下來需從剩余容量c-w1中尋求最優(yōu)解，用f(2,c-w1)表示最優(yōu)解。依此類推，可得到所有的xi(i=1.n)值。在該例中，可得出f(2,116)=33≠f(1,116)，所以x1=1。接著利用返回值38-p1=18計算x2及x3，此時r=116-w1=16，又由f(2,16)=18，得f(3,16)=14≠f(2,16)，因此x2=1，此時r=16-w2=2，所以f(3,2)=0，即得x3=0代碼如下;#include<cstdlib>#include<iostream>#include"math.h"usingnamespacestd;intw[5]={2,2,6,5,4};intv[5]={6,3,5,4,6};intlength=5;intc=10;intm[5][10];voidknapsack(int*v,int*w,intc,intm[][10]){intn=length-1;intjMax=min(w[n]-1,c);for(intj=0;j<=jMax;j++){m[n][j]=0;}for(intj=w[n];j<=c;j++){m[n][j]=v[n];}for(inti=n-1;i>1;i--){jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//背包容量沒有i物品大，則從i-n選物品裝入包的中價值等于從i+1~nm[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//包可以裝入i,則分兩種情況，一種是裝i，一種是不裝i，從中選最大}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[1][c-w[1]]+v[1]);}voidtraceback(intm[][10],int*w,intc,int*x){intn=length-1;for(inti=0;i<n;i++){if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}}x[n]=(m[n][c]>0)?1:0;}intmain(intargc,char*argv[]){intx[5];knapsack(v,w,c,m);traceback(m,w,c,x);for(inti=0;i<5;i++){if(x[i]==1)printf("%d",w[i]);}//printf("%d",x[i]);system("PAUSE");returnEXIT_SUCCESS;}實驗三：用分支限界法實現(xiàn)0/1背包問題。算法分析：采用分支限定法，對物品的選取與否構(gòu)成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優(yōu)解，并用結(jié)點上界殺死不符合要求的結(jié)點。代碼如下：#include"stdlib.h"#include"math.h"#include"iostream"usingnamespacestd;//子集空間樹結(jié)點classbbnode{friendclassKnap;friendintKnapsack(intp[],intw[],intc,intn,intbestx[]);private:bbnode*parent;//指向父結(jié)點的指針boolLChild;//左兒子結(jié)點標(biāo)志};//對大堆結(jié)點classHeapNode{friendclassKnap;public:operatorint()const{returnuprofit;}intuprofit,//結(jié)點的價值上界profit;//結(jié)點所相應(yīng)的價值intweight;//結(jié)點所相應(yīng)的重量intlevel;//活結(jié)點在子集樹種所處的層序號bbnode*ptr;//指向活結(jié)點在子集樹種相應(yīng)結(jié)點的指針};typedefstructHeap{intcapacity;intsize;HeapNode*Elem;}Heap,*MaxHeap;MaxHeapinitH(intmaxElem){MaxHeapH;H=(MaxHeap)malloc(sizeof(Heap));H->capacity=maxElem;H->Elem=(HeapNode*)malloc((maxElem)*sizeof(HeapNode));H->size=0;returnH;}voidInsertH(HeapNodex,MaxHeapH){inti,sindex=0;for(i=0;i<H->size;i++){if(H->Elem[i].uprofit>=x.uprofit){sindex=i;break;}}for(i=H->size;i>sindex;i--){H->Elem[i]=H->Elem[i-1];}H->Elem[sindex]=x;H->size++;}HeapNodeDeleteMaxH(MaxHeapH){returnH->Elem[--H->size];}voidDestoryH(MaxHeapH){free(H->Elem);free(H);}classObject{friendintKnapsack(intp[],intw[],intc,intn,intbestx[]);public:intoperator<=(Objecta)const{return(d>=a.d);}private:intID;floatd;//單位重量價值};classKnap{friendintKnapsack(intp[],intw[],intc,intn,intbestx[]);public:intMaxKnapsack();private:MaxHeapH;intBound(inti);voidAddLiveNode(intup,intcp,intcw,boolch,intlevel);bbnode*E;//指向擴展結(jié)點的指針intc;//背包容量intn;//物品數(shù)int*w;//物品重量數(shù)組int*p;//物品價值數(shù)組intcw;//當(dāng)前裝包重量intcp;//當(dāng)前裝包價值int*bestx;//最優(yōu)解};intKnap::Bound(inti){//計算節(jié)點所相應(yīng)價值的上界intcleft=c-cw;//剩余容量intb=cp;//價值上界//以物品單位重量價值遞減序裝填剩余容量while(i<n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}if(i<=n){b+=p[i]*cleft/w[i];}returnb;}voidKnap::AddLiveNode(intup,intcp,intcw,boolch,intlev){//將一個新的活結(jié)點插入到子集樹和最大堆H中bbnode*b=newbbnode;b->parent=E;b->LChild=ch;HeapNodeN;N.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;InsertH(N,H);}intKnap::MaxKnapsack(){//優(yōu)先隊列式分支限界法，返回最大價值，bestx返回最優(yōu)解//定義對大堆得容量為H=initH(1000);bestx=newint[n];//初始化inti=0;E=0;cw=cp=0;intbestp=0;//當(dāng)前最優(yōu)值intup=Bound(0);//價值上界//搜索子集空間樹while(i!=n){//檢查當(dāng)前擴展結(jié)點的左兒子節(jié)點intwt=cw+w[i];if(wt<=c){//左兒子節(jié)點為可行結(jié)點if(cp+p[i]>bestp){bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);}//檢查當(dāng)前擴展結(jié)點的右兒子節(jié)點if(up>=bestp){AddLiveNode(up,cp,cw,false,i+1);}//取下一擴展結(jié)點HeapNodeN;N=DeleteMaxH(H);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit;i=N.level;}//構(gòu)造當(dāng)前最優(yōu)解for(i=n-1;i>=0;i--){bestx[i]=E->LChild;E=E->parent;}DestoryH(H);returncp;}intKnapsack(intp[],intw[],intc,intn,intbestx[]){//返回最大價值，bestx返回最優(yōu)解intW=0;intP=0;inti,j,max;Object*Q=newObject[n];Objectqtmp;for(i=0;i<n;i++){Q[i].ID=i;Q[i].d=1.0*p[i]/w[i];W+=w[i];P+=p[i];}if(W<=c){returnP;//裝入所有物品}//依物品單位重量價值排序for(i=0;i<n;i++){max=i;for(j=i+1;j<n;j++){if(Q[max].d<Q[j].d){max=j;}}qtmp=Q[i];Q[i]=Q[max];Q[max]=qtmp;}KnapK;K.p=newint[n];K.w=newint[n];for(i=0;i<n;i++){K.p[i]=p[Q[i].ID];K.w[i]=w[Q[i].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;intbestp=K.MaxKnapsack();for(i=0;i<n;i++){bestx[Q[i].ID]=K.bestx[i];}delete[]Q;delete[]K.w;delete[]K.p;delete[]K.bestx;returnbestp;}#definen5//物品的數(shù)量//物體重量、收益、背包容量intweight[n],profit[n],contain,x[n];//從文件中讀取背包信息intread_infor(){FILE*fp;inti;if((fp=fopen("knapsack.txt","r"))==NULL){printf("Thefileisnotfound!");return0;}//讀取物體收益信息for(i=0;i<n;i++){fscanf(fp,"%d,",&profit[i]);}/*profit[0]=6;profit[1]=3;profit[2]=5;profit[3]=4;profit[4]=6;weight[0]=2;weight[1]=2;weight[2]=6;weight[3]=5;weight[4]=4;contain=10;*///讀取物體重量信息，計算物體的單位重量價值for(i=0;i<n;i++){fscanf(fp,"%d,",&weight[i]);}//讀取背包容量fscanf(fp,"%d",&contain);fclose(fp);return1;}intmain(){intresult;if(read_infor()){result=Knapsack(profit,weight,contain,n,x);printf("Themaximumprofitis:%d.\n",result);for(inti=0;i<n;i++)printf("%d",x[i]);}scanf("%d",&result);return0;}實驗四：用深度優(yōu)化的方法遍歷一個圖，并判斷圖中是否有回路存在，如果有，請輸出回路。算法分析:采用深度優(yōu)先連理一個圖，每個節(jié)點有一個visited[n]值，初始為0，,每次被遍歷1次，visited[n]++，如果發(fā)現(xiàn)visited[n]值為2，則將fag的值置為1，說明圖中存在環(huán)，如果遍歷結(jié)束，fag=0，則說明圖中沒有環(huán)。代碼：#include<stdio.h>#include<stdlib.h>#include<iostream>usingnamespacestd;typedefintStatus;//圖的結(jié)構(gòu)部分，使用鄰接表來描述#defineMAX_VERTEX_NUM20typedefcharInfoType;typedefcharVertexType;typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}arcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstructALGraph{AdjListvertics;intvexnum,arcnum;//圖的當(dāng)前頂點和和弧數(shù)intkind;//圖的種類標(biāo)志}ALGraph;//開始DFSintvisited[MAX_VERTEX_NUM];//聲明訪問全局標(biāo)志intfag=0;//聲明環(huán)存在與否標(biāo)志StatusDFS(ALGraphG,intn)//深度優(yōu)先方式從頂點n開始遍歷G{visited[n]=2;//標(biāo)志visited[n]為在當(dāng)前訪問的路徑上intk;ArcNode*p=NULL;//弧節(jié)點指針if(fag){//如果已經(jīng)被設(shè)置為1了就沒有必要再判斷了，退出函數(shù)visited[n]=1;//退出前先標(biāo)志為訪問過return0;}for(p=G.vertics[n].firstarc;p;p=p->nextarc){k=p->adjvex;//取出當(dāng)前后繼頂點if(visited[k]==2){//如果當(dāng)前后繼頂點的visited標(biāo)志為2，即當(dāng)前后繼頂點在當(dāng)前訪問的路徑上，說明存在環(huán)fag=1;//設(shè)置環(huán)存在與否標(biāo)志為1，即存在環(huán)return1;//直接返回}if(!visited[k])DFS(G,k);}visited[n]=1;//標(biāo)志為訪問過return1;}//主算法Statusexistring(ALGraphG)//深度優(yōu)先方式判斷有向圖G是否存在環(huán){inti;fag=0;//初始化環(huán)存在與否標(biāo)志，初始為不存在for(i=0;i<MAX_VERTEX_NUM;++i){//初始化visited[]數(shù)組，標(biāo)志所以的頂點都未曾訪問visited[i]=0;}for(i=0;i<G.vexnum;++i){DFS(G,i);//對所有的節(jié)點調(diào)用DFS函數(shù)if(fag)break;//已經(jīng)證明存在環(huán)就直接退出循環(huán)}returnfag;//返回環(huán)存在與否標(biāo)志}//輸出voiddisALGraph(ALGraphG)//顯示圖G{inti,k;ArcNode*p=NULL;//弧節(jié)點指針for(i=0;i<G.vexnum;++i){cout<<G.vertics[i].data;for(p=G.vertics[i].firstarc;p;p=p->nextarc){//輸出后繼頂點k=p->adjvex;cout<<"->";cout<<G.vertics[k].data;}cout<<endl;}}//測試部分intmain(){ALGraphG;//聲明鄰接表變量G.arcnum=0;//初始化G.kind=0;//有向圖arcNode*p=NULL;//聲明弧節(jié)點指針charit;//輸入緩存charc;cout<<"輸入頂點數(shù)目:"<<endl;cin>>G.vexnum;//輸入頂點數(shù)目if(G.vexnum<1||G.vexnum>=MAX_VERTEX_NUM){cout<<"輸入錯誤!\n";return0;}//開始創(chuàng)建Gfor(inti=0;i<G.vexnum;++i){G.vertics[i].data='A'+i;//為了簡單起見設(shè)頂點是ABCDEFGH....G.vertics[i].firstarc=NULL;//初始化指向第一條弧的指針firstarcit=1;//為了下面的輸入順利進行while(it!='Z'){cout<<"輸入"<<G.vertics[i].data<<"的指向(Z鍵結(jié)束):";cin>>it;//cout<<it<<endl;if((it-'A')!=i&&int(it-'A'+1)<=G.vexnum&&int(it-'A'+1)>0){//添加的弧符合指向的話就添加并顯示p=newarcNode;p->adjvex=int(it-'A');p->info=NULL;p->nextarc=G.vertics[i].firstarc;G.vertics[i].firstarc=p;c=it;cout<<"成功添加:"<<G.vertics[i].data<<"->"<<c<<endl;}//else{//cout<<"輸入有誤！"<<endl;//}}}//創(chuàng)建完成cout<<"\n鄰接表試圖:"<<endl;disALGraph(G);//輸出Gif(fag=0){//判斷G是否存在環(huán)cout<<"該圖中不存在環(huán)！"<<endl;}elseif(fag=1){cout<<"該圖中存在環(huán)！"<<endl;}//cout<<"\n判斷結(jié)果(0:不存在,1:存在):"<<ex