回溯法试验最大团问题

1、算法分析与设计实验报告匕次附加实验姓名学号班级时间上午地点工训楼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中所含顶点数最多的团。实验原理G中，所以由于（1,3 ）之间没有连线，1,2,

2、3）（ 1,5,4）（2,3,4）都是因此（1,2,3）（ 1,5,4）（ 2,3,4）由上图来看，（1,2,4）中每个顶点之间都相连接，并且都包含在图（1,2,4）是一个图 G的一个团，但是（1,2,3,4） 所以没有保证所有顶点都连接，因此不是团，而（ 三顶点的团，而该图包含顶点数最多的团就是三个， 属于最大团，最大团问题就是求解这样的问题。程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数，可停止继续深度搜索， 否则继续深度递归当搜索到一个叶结点时，即可停止搜索，此时更新最优解和最优值。基本解题步骤：（1）针对所给问题，定义问题的解空间；（2）

3、确定易于搜索的解空间结构； 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。(1) 首先设最大团为一个空团，往其中加入一个顶点；实验步骤(2) 然后依次考虑每个顶点，查看该顶点加入团之后仍然构成一个团，如果 可以，考虑将该顶点加入团或者舍弃两种情况，如果不行，直接舍弃，然后递 归判断下一顶点；(3) 可采用剪枝策略来避免无效搜索；(4) 为了判断当前顶点加入团之后是否仍是一个团，只需要考虑该顶点和团 中顶点是否都有连接。void Clique:Backtrack(nt i) /计算最大团if(i> n) /到达叶子节点for(i nt j=1;jv=n ;j+) best

4、xj=xj;best n=cn;cout<<'最大团：("for(i nt i=1;i< n;i+) cout<<bestxi<<"," cout<<bestx n <<")" we ndl;retur n;/检查当前顶点是否与当前团连接int ok=1;for(i nt j=1;j<i;j+)关键代码if(xj&&aij=0) /i与j不连接，即j在团中，但是i,j不连接 ok=0;break; if(ok) /进入左子树xi=1;cn+;Back

5、track(i+1);/回溯到下一层节点xi=0;cn-;/通过上界函数判断是否减去右子树，上界函数用于确认还有 足够多的可选择顶点使得算法有可能在右子树中找到更大的团if(c n+n-i>=best n)/修改一下上界函数的条件，可以得到xi=0;/相同点数时的解Backtrack(i+1);H当输入图如下时:p-F：算法实密.实验囚回j®SM axCliq ueDe bu giMa xCl iq ue, exeplease please Lp lease kinput input Imput edge:number of node:G number of edge：?245

6、3445团：(1,1,0,1,0>5：(1,0,0,1,i>S： (0,1,1,1,0>任忌键维续-测试结果当输入图如下时:pplease please please i12343445number of nodeinputinput nunbep of edge：8inputedsfe :点继 (i 1慰娶冃5当输入图如下时:I E F;算法实验实验四回滋法M axCl i qu eDeb u gM axCii q u e.exeInput nunber of node input nunbei' of edge ：9Ase input edsfe =2I Mr?

7、j_ I d I I请按任意键继類-通过三个实例图，我们只是简单的将最开始的原始图进行加边处理，可以实验分析发现结果就会发生变化。 最大团问题可是比较典型的利用解空间的子集树进行 深度搜索，然后通过上界函数进行剪枝，只是此处的上界函数比较简单，只要判断是否还有做够的顶点能够构成最大团即可，相对于0-1背包问题和最优装载问题来说还是简单一点，其中主要注意的就是要加入现有团的顶点必须满足 和所有的团内的顶点都有边相连，这样才能加入该团中，否则就不能加入团中。最大团问题和图的 m着色问题用回溯法解很相似，他俩在对于判断的时 候都比较简单，但是相比而言，由于最大团问题涉及到利用上届函数进行右子 树剪枝

8、，所以相比较而言复杂一点， 最大团问题的上届函数和很多问题比如最 优装载问题的上届函数原理是相同的，就是判断右子树当前节点最好的可能是实验心得否能够比当前最优解要好，如果当前节点的最好情况都不能超过当前最优解， 那么说明最优解绝对不会有该节点，因此可以将该节点所在的右子树剪掉，这样就减少了算法的查找和回溯的时间。这里要提一点的是在进行右子树剪枝的时候使用了大于等于，如果只是大于的话就没有办法找到顶点数相同的其他最 优解了，同样找到叶子节点时则证明得到一个最优解，将其输出即可实验得分助教签名附录： 完整代码(回溯法)/ 最大团问题 回溯法求解 #include<iostream>us

9、ing namespacestd;classCliquefriend void MaxClique(int *, int *,int ); private:void Backtrack(int i); int *a; / 图的邻接矩阵 int n; / 图的顶点数 int *x; / 当前解 int *bestx; / 当前最优解 int cn; / 当前顶点数 int bestn; / 当前最大顶点数;void Clique:Backtracki(nt i) / 计算最大团 if (i>n) / 到达叶子节点for(int j=1;j<=n;j+) bestxj=xj;bestn

10、=cn; cout<<" 最大团：( " for(int i=1;i<n;i+) cout<<bestxi<<"," ; cout<<bestxn<<")" <<endl;return ;/ 检查当前顶点是否与当前团连接int ok=1;for(int j=1;j<i;j+)if(xj&&aij=O) /i与j不连接,即j在团中，但是i,j不连接 ok=O;break;if(ok) /进入左子树xi=1;cn+;Backtrack(i+

11、1);/回溯到下一层节点 xi=O;cn-;/ 通过上界函数判断是否减去右子树， 上界函数用于确认还有足够多的可选 择顶点使得算法有可能在右子树中找到更大的团if (cn+n-i>=bestn) / 修改一下上界函数的条件，可以得到xi=0; / 相同点数时的解Backtrack(i+1);void MaxClique(int *a, int *v,int n) / 初始化 YClique Y;=new int n+1;=a;=n;=0;=0;=v;(1);delete ;cout<<" 最大团的顶点数： " <<<<endl;in

12、t main()int n;cout<<"please input number of node:" ;cin>>n;/int an+1n+1; / 由于定义的是 int *a ，且采用的是二维数组传参，因此 int *a= new int *n+1; / 两种解决方法，一是给定第二维的大小，二是通过 for(int i=0;i<=n;i+) / 动态分配内存，这里采用了动态内存分配解决问题 ai=new intn+1;for(int i=0;i<n+1;i+)for (int j=0;j<n+1;j+)aij=0;int edge;cout<<"please input number of edge:"cin>>edge;c