最大团问题-回溯法.ppt

,最大团问题回溯法,Theauthor：王志红,目录contents,One,回溯法基本思想,Two,问题描述,Three,算法设计,Six,算法度量,Seven,改进,Four,代码示例,Five,实例分析,Eight,应用,01回溯法基本思想.,回溯法按照深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死结点。此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点。回溯法以这种方式递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点为止。,02,回溯法基本思想,01,问题描述,给定无向图G=(V，E)。如果UV，且对任意u，vU有(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的最大团。,02问题描述,03算法设计,无向图G的最大团问题可以看作是图G的顶点集V的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点Z位于解空间树的第i层。在进入左子树前，必须确认从顶点i到已入选的顶点集中每一个顶点都有边相连。在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。用邻接矩阵表示图G，n为G的顶点数，cn存储当前团的顶点数，bestn存储最大团的顶点数。cn+n-i为进入右子树的上界函数，当cn+n-in)/到达叶子节点for(intj=1;jbestn)/通过上界函数判断是否减去右子树xi=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=1cn=0bestn=0,i=2cn=1bestn=0,i=3cn=2bestn=0,i=4cn=2bestn=0,i=6cn=3bestn=3,i=3cn=1bestn=3,i=1cn=0bestn=3,i=4cn=2bestn=3,i=2cn=0bestn=3,i=3cn=1bestn=3,i=5cn=2bestn=0,05实例分析,06算法度量,07改进,选择合适的搜索顺序，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。定义Si=vi,vi+1,.,vn，依次求出Sn,Sn-1,.,S1的解。