算法实验报告14700字

算法实验报告14700字

中南大学算法设计与分析实验报告学生姓名惠苗壮指导教师郑瑾专业班级计科0904班学号0909091627完成时间20xx年12月18日学院信息科学与工程学院目录一．实验目的???????????????1二．实验要求???????????????1三．实验内容???????????????1四．实验分析???????????????1五．实验结果???????????????15六．实验心得???????????????20一．实验目的：1.掌握动态规划、回溯法、分支限定法的原理。2.能独立完成上述算法的实现。3.能用上述算法解决问题。二．实验要求：1.给出相应的测试结果。2.给出源代码及相应的注释。3.所有的输入和输出都用文件处理。三．实验内容：1.实现求n皇后问题和子集和数问题的回溯算法。2.用动态规划的方法实现0/1背包问题。3.用分支限界法实现0/1背包问题。4.用深度优化的方法遍历一个图，并判断图中是否有回路存在，如果有，请输出回路。四．实验分析：实验一：实现求n皇后问题和子集和数问题的回溯算法。问题说明：按照国际象棋的规则在N*N的棋盘上放置彼此不受攻击的皇后问题。数据表示：用n个数彼此用“，”隔开来表示那个皇后的最后位置，如：4皇后问题中，最后结果为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行当前列是否可以放置皇后{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");实验二：用动态规划的方法实现0/1背包问题。问题说明：给定n种物品和一背包。物品i的重量是w，其价值是v，背包的容量为C。求应怎样装入物体使得装入背包中的物体总价值最大。算法说明:采用动态规划的方法，将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。在该问题中需要决定x1..xn的值。假设按i=1，2，...，n的次序来确定xi的值。如果置x1=0，则问题转变为相对于其余物品(即物品2，3，.，n)，背包容量仍为c的背包问题。若置x1=1，问题就变为关于最大背包容量为c-w1的问题。现设r?{c，c-w1}为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。不管x1是0或是1，[x2，.，xn]必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn]，因而[x1，y2，.，yn]是一个更好的方案。假设n=3,w=[100,14,10],p=[20,18,15],c=116。若设x1=1，则在本次决策之后，可用的背包容量为r=116-100=16。[x2，x3]=[0,1]符合容量限制的条件，所得值为15，但因为[x2，x3]=[1，0]同样符合容量条件且所得值为18，因此[x2，x3]=[0，1]并非最优策略。即x=[1，0，1]可改进为x=[1，1，0]。若设x1=0，则对于剩下的两种物品而言，容量限制条件为116。总之，如果子问题的结果[x2，x3]不是剩余情况下的一个最优解，则[x1，x2，x3]也不会是总体的最优解。在此问题中，最优决策序列由最优决策子序列组成。假设f(i,y)表示剩余容量为y，剩余物品为i，i+1，...，n时的最优解的值，即：利用最优序列由最优子序列构成的结论，可得到f的递归式为：当j>=wi时：f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi}①式当0<=j时：fn(1,c)是初始时背包问题的最优解。以本题为例：若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)。因此最优解f(1,116)=max{f(2，116)，f(2，116-w1)+p1}=max{f(2，116)，f(2，16)+20}=max{33，38}=38。现在计算xi值，步骤如下：若f(1,c)=f(2,c)，则x1=0，否则x1=1。接下来需从剩余容量c-w1中寻求最优解，用f(2,c-w1)表示最优解。依此类推，可得到所有的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;}实验三：用分支限界法实现0/1背包问题。算法分析：采用分支限定法，对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。代码如下：#include"stdlib.h"#include"math.h"#include"iostream"usingnamespacestd;//子集空间树结点classbbnode{friendclassKnap;friendintKnapsack(intp[],intw[],intc,intn,intbestx[]);private:bbnode*parent;//指向父结点的指针boolLChild;//左儿子结点标志};//对大堆结点classHeapNode{friendclassKnap;public:operatorint()const{returnuprofit;}intuprofit,//结点的价值上界profit;//结点所相应的价值intweight;//结点所相应的重量intlevel;//活结点在子集树种所处的层序号bbnode*ptr;//指向活结点在子集树种相应结点的指针};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;//指向扩展结点的指针intc;//背包容量intn;//物品数int*w;//物品重量数组int*p;//物品价值数组intcw;//当前装包重量intcp;//当前装包价值int*bestx;//最优解};intKnap::Bound(inti){//计算节点所相应价值的上界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){//将一个新的活结点插入到子集树和最大堆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(){//优先队列式分支限界法，返回最大价值，bestx返回最优解//定义对大堆得容量为H=initH(1000);bestx=newint[n];//初始化inti=0;E=0;cw=cp=0;intbestp=0;//当前最优值intup=Bound(0);//价值上界//搜索子集空间树while(i!=n){//检查当前扩展结点的左儿子节点intwt=cw+w[i];if(wt<=c){//左儿子节点为可行结点if(cp+p[i]>bestp){bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);}//检查当前扩展结点的右儿子节点if(up>=bestp){AddLiveNode(up,cp,cw,false,i+1);}//取下一扩展结点HeapNodeN;N=DeleteMaxH(H);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit;i=N.level;}//构造当前最优解for(i=n-1;i>=0;i--){bestx[i]=E->LChild;E=E->parent;}DestoryH(H);returncp;}intKnapsack(intp[],intw[],intc,intn,intbestx[]){//返回最大价值，bestx返回最优解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//物品的数量//物体重量、收益、背包容量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;}实验四：用深度优化的方法遍历一个图，并判断图中是否有回路存在，如果有，请输出回路。算法分析:采用深度优先连理一个图，每个节点有一个visited[n]值，初始为0，,每次被遍历1次，visited[n]++，如果发现visited[n]值为2，则将fag的值置为1，说明图中存在环，如果遍历结束，fag=0，则说明图中没有环。代码：#include<stdio.h>#include<stdlib.h>#include<iostream>usingnamespacestd;typedefintStatus;//图的结构部分，使用邻接表来描述#defineMAX_VERTEX_NUM20typedefcharInfoType;typedefcharVertexType;typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}arcNode;typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstructALGraph{AdjListvertics;intvexnum,arcnum;//图的当前顶点和和弧数intkind;//图的种类标志}ALGraph;//开始DFSintvisited[MAX_VERTEX_NUM];//声明访问全局标志intfag=0;//声明环存在与否标志StatusDFS(ALGraphG,intn)//深度优先方式从顶点n开始遍历G{visited[n]=2;//标志visited[n]为在当前访问的路径上intk;ArcNode*p=NULL;//弧节点指针if(fag){//如果已经被设置为1了就没有必要再判断了，退出函数visited[n]=1;//退出前先标志为访问过return0;}for(p=G.vertics[n].firstarc;p;p=p->nextarc){k=p->adjvex;//取出当前后继顶点if(visited[k]==2){//如果当前后继顶点的visited标志为2，即当前后继顶点在当前访问的路径上，说明存在环fag=1;//设置环存在与否标志为1，即存在环return1;//直接返回}if(!visited[k])DFS(G,k);}visited[n]=1;//标志为访问过return1;}//主算法Statusexistring(ALGraphG)//深度优先方式判断有向图G是否存在环{inti;fag=0;//初始化环存在与否标志，初始为不存在for(i=0;i<MAX_VERTEX_NUM;++i){//初始化visited[]数组，标志所以的顶点都未曾访问visited[i]=0;}for(i=0;i<G.vexnum;++i){DFS(G,i);//对所有的节点调用DFS函数if(fag)break;//已经证明存在环就直接退出循环}returnfag;//返回环存在与否标志}//输出voiddisALGraph(ALGraphG)//显示图G{inti,k;ArcNode*p=NULL;//弧节点指针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;//声明弧节点指针charit;//输入缓存charc;cout<<"输入顶点数目:"<<endl;cin>>G.vexnum;//输入顶点数目if(G.vexnum<1||G.vexnum>=MAX_VERTEX_NUM){cout<<"输入错误!\n";return0;}//开始创建Gfor(inti=0;i<G.vexnum;++i){G.vertics[i].data='A'+i;//为了简单起见设顶点是ABCDEFGH....G.vertics[i].firstarc=NULL;//初始化指向第一条弧的指针firstarcit=1;//为了下面的输入顺利进行while(it!='Z'){cout<<"输入"<<G.vertics[i].data<<"的指向(Z键结束):";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;//}}}//创建完成cout<<"\n邻接表试图:"<<endl;disALGraph(G);//输出Gif(fag=0){//判断G是否存在环cout<<"该图中不存在环！"<<endl;}elseif(fag=1){cout<<"该图中存在环！"<<endl;}//cout<<"\n判断结果(0:不存在,1:存在):"<<ex