最大团问题-回溯法.ppt

单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,最大团问题,回溯法,The author,：王志红,.,目录,contents,One,回溯法基本思想,Two,问题描述,Three,算法设计,Six,算法度量,Seven,改 进,Four,代码示例,Five,实例分析,Eight,应 用,.,01,回溯法基本思想,.,回溯法按照深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死结点。此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点。,回溯法以这种方式递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点为止。,02,回,溯,法,基,本,思,想,.,01,问题描述,给定无向图,G=(V,，,E),。如果,U,V,，且对任意,u,，,v,U,有,(u,，,v),E,，则称,U,是,G,的完全子图。,G,的完全子图,U,是,G,的团当且仅当,U,不包含在,G,的更大的完全子图中。,G,的最大团是指,G,中所含顶点数最多的团。,下图,G,中，子集,1,，,2,是,G,的大小为,2,的完全子图。这个完全子图不是团，因为它被,G,的更大的完全子图,1,，,2,，,5,包含。,1,，,2,，,5,是,G,的最大团。,1,，,4,，,5,和,2,，,3,，,5,也是,G,的最大团。,1,2,4,5,3,02,问题描述,.,03,算法设计,无向图,G,的最大团问题可以看作是图,G,的顶点集,V,的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点,Z,位于解空间树的第,i,层。在进入左子树前，必须确认从顶点,i,到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。,用邻接矩阵表示图,G,，,n,为,G,的顶点数，,cn,存储当前团的顶点数，,bestn,存储最大团的顶点数。,cn+n-i,为进入右子树的上界函数，当,cn+n-in),/,到达叶子节点,for,(,int,j=1;j=n;j+),bestxj=xj;,bestn=cn;,return,;,/,检查当前顶点是否与当前团连接,int,ok=1;,for,(,int,j=1;jbestn),/,通过上界函数判断是否减去右子树,x,i,=0;Backtrack(,i,+1);,.,03,MCP,回溯法详细介绍,1,1,3,2,2,2,4,3,3,3,3,3,3,4,3,4,4,2,4,4,4,4,4,4,4,4,4,4,4,4,R,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,根节点,i=1 cn=0 bestn=0,i=2 cn=1 bestn=0,i=3 cn=2 bestn=0,i=4 cn=2 bestn=0,i=6 cn=3 bestn=3,i=3 cn=1 bestn=3,i=1 cn=0 bestn=3,i=4 cn=2 bestn=3,i=2 cn=0 bestn=3,i=3 cn=1 bestn=3,1,2,4,5,3,i=5 cn=2 bestn=0,05,实例分析,.,Company Logo,06,算法度量,1,时间复杂度,由于最大团问题是一个子集树问题，每个可行叶结点都做一次,bestx,更新，因此可知算法的时间复杂度,O(n2,n,),2,空间复杂度,在程序中使用邻接矩阵才存储图，用两个一维数组存储当前解和最优解信息，因此可知所用的存储空间,O(n,2,),由于程序采用递归搜索，因此递归也占用了一定的栈空间,.,07,改进,选择合适的搜索顺序，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。,定义,Si=vi,vi+1,.,vn,，依次求出,Sn,Sn-1,.,S1,的解。从而得到一个更精确的上界函数，若,cn+Si=bestn,.,.,.,.,