回溯法实验(最大团问题)

算法分析与设计实验报告第七次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称回溯法实验(最大团问题)实验目的1.掌握回溯法求解问题的思想2.学会利用其原理求解最大团问题实验原理问题描述：给定无向连通图G=（V,E），其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“（）”表示，如果UϵV，且对任意两个顶点u，vϵU有（u,v）ϵE，则称U是G的完全子图，G的完全子图是G的团当前仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。由上图来看，（1,2,4）中每个顶点之间都相连接，并且都包含在图G中，所以（1,2,4）是一个图G的一个团，但是（1,2,3,4）由于（1,3）之间没有连线，所以没有保证所有顶点都连接，因此不是团，而（1,2,3）（1,5,4）（2,3,4）都是三顶点的团，而该图包含顶点数最多的团就是三个，因此（1,2,3）（1,5,4）（2,3,4）属于最大团，最大团问题就是求解这样的问题。程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数，可停止继续深度搜索，否则继续深度递归当搜索到一个叶结点时，即可停止搜索，此时更新最优解和最优值。基本解题步骤：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。12345实验步骤（1）首先设最大团为一个空团，往其中加入一个顶点；（2）然后依次考虑每个顶点，查看该顶点加入团之后仍然构成一个团，如果可以，考虑将该顶点加入团或者舍弃两种情况，如果不行，直接舍弃，然后递归判断下一顶点；（3）可采用剪枝策略来避免无效搜索；（4）为了判断当前顶点加入团之后是否仍是一个团，只需要考虑该顶点和团中顶点是否都有连接。关键代码voidClique::Backtrack(inti){//计算最大团if(in)//到达叶子节点{for(intj=1;j=n;j++)bestx[j]=x[j];bestn=cn;cout最大团：（;for(inti=1;in;i++)coutbestx[i],;coutbestx[n])endl;return;}//检查当前顶点是否与当前团连接intok=1;for(intj=1;ji;j++)if(x[j]&&a[i][j]==0)//i与j不连接,即j在团中,但是i,j不连接{ok=0;break;}if(ok)//进入左子树{x[i]=1;cn++;Backtrack(i+1);//回溯到下一层节点x[i]=0;cn--;}//通过上界函数判断是否减去右子树，上界函数用于确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团if(cn+n-i=bestn){//修改一下上界函数的条件，可以得到x[i]=0;//相同点数时的解Backtrack(i+1);}}测试结果当输入图如下时：当输入图如下时：1234512345当输入图如下时：12345附录：完整代码（回溯法）//最大团问题回溯法求解#includeiostreamusingnamespacestd;classClique{friendvoidMaxClique(int**,int*,int);private:voidBacktrack(inti);int**a;//图的邻接矩阵intn;//图的顶点数int*x;//当前解int*bestx;//当前最优解intcn;//当前顶点数intbestn;//当前最大顶点数};voidClique::Backtrack(inti){//计算最大团if(in)//到达叶子节点{for(intj=1;j=n;j++)bestx[j]=x[j];bestn=cn;实验分析通过三个实例图，我们只是简单的将最开始的原始图进行加边处理，可以发现结果就会发生变化。最大团问题可是比较典型的利用解空间的子集树进行深度搜索，然后通过上界函数进行剪枝，只是此处的上界函数比较简单，只要判断是否还有做够的顶点能够构成最大团即可，相对于0-1背包问题和最优装载问题来说还是简单一点，其中主要注意的就是要加入现有团的顶点必须满足和所有的团内的顶点都有边相连，这样才能加入该团中，否则就不能加入团中。实验心得最大团问题和图的m着色问题用回溯法解很相似，他俩在对于判断的时候都比较简单，但是相比而言，由于最大团问题涉及到利用上届函数进行右子树剪枝，所以相比较而言复杂一点，最大团问题的上届函数和很多问题比如最优装载问题的上届函数原理是相同的，就是判断右子树当前节点最好的可能是否能够比当前最优解要好，如果当前节点的最好情况都不能超过当前最优解，那么说明最优解绝对不会有该节点，因此可以将该节点所在的右子树剪掉，这样就减少了算法的查找和回溯的时间。这里要提一点的是在进行右子树剪枝的时候使用了大于等于，如果只是大于的话就没有办法找到顶点数相同的其他最优解了，同样找到叶子节点时则证明得到一个最优解，将其输出即可实验得分助教签名cout最大团：（;for(inti=1;in;i++)coutbestx[i],;coutbestx[n])endl;return;}//检查当前顶点是否与当前团连接intok=1;for(intj=1;ji;j++)if(x[j]&&a[i][j]==0)//i与j不连接,即j在团中,但是i,j不连接{ok=0;break;}if(ok)//进入左子树{x[i]=1;cn++;Backtrack(i+1);//回溯到下一层节点x[i]=0;cn--;}//通过上界函数判断是否减去右子树，上界函数用于确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团if(cn+n-i=bestn){//修改一下上界函数的条件，可以得到x[i]=0;//相同点数时的解Backtrack(i+1);}}voidMaxClique(int**a,int*v,intn){//初始化YCliqueY;Y.x=newint[n+1];Y.a=a;Y.n=n;Y.cn=0;Y.bestn=0;Y.bestx=v;Y.Backtrack(1);delete[]Y.x;cout最大团的顶点数：Y.bestnendl;}intmain(){intn;coutpleaseinputnumberofnode:;cinn;//inta[n+1][n+1];//由于定义的是int**a，且采用的是二维数组传参，因此int**a=newint*[n+1];//两种解决方法，一是给定第二维的大小，二是通过for(inti=0;i=n;i++)//动态分配内存，这里采用了动态内存分配解决问题a[i]=newint[n+1];for(inti=0;in+1;i++)for(intj=0;jn+1;j++)a[i][j]=0;intedge;coutpleaseinputnumberofedge:;cinedge;coutpleaseinputedge:endl;intv,w;for(inti=0;iedge;i++){cinvw;a[v][w]=1;a[w][v]=1;}int*p=newint[n+1];MaxClique(a,p,n);system(pause);return0;}