最大团问题-回溯法.ppt

1、,最大团问题 回溯法,The author ：王志红,目录 contents,One,回溯法基本思想,Two,问题描述,Three,算法设计,Six,算法度量,Seven,改 进,Four,代码示例,Five,实例分析,Eight,应 用,01 回溯法基本思想.,回溯法按照深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至

2、一个新节点。这个新节点就成为一个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死结点。此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点。 回溯法以这种方式递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点为止。,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的完全子图。这个完全子图不

3、是团，因为它被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-ibestn时，不能在右子

4、树中找到更大的团，可将Z的右节点剪去。,解空间：子集树 可行性约束函数：顶点i到已选入的顶点集中每一个顶点都有边相连。 上界函数：有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。,04 代码示例,void Clique:Backtrack(int i) /计算最大团 if(in) /到达叶子节点 for(int j=1;jbestn) /通过上界函数判断是否减去右子树 xi=0; Backtrack(i+1); ,03,MCP回溯法详细介绍,Company Logo,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

5、,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,i=5 cn=2 bestn=0,05 实例分析,06 算法度量,07 改进,选择合适的搜索顺序，可以使得上界函数更有效

6、的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。 定义Si=vi,vi+1,.,vn，依次求出Sn,Sn-1,.,S1的解。从而得到一个更精确的上界函数，若cn+Si=max则剪枝。同时注意到：从Si+1到Si，如果找到一个更大的团，那么vi必然属于找到的团，此时有Si=Si+1+1，否则Si=Si+1。因此只要max的值被更新过，就可以确定已经找到最大值，不必再往下搜索了。,08 应用,最大团问题是图论中的一个经典组合优化问题，也是一类NP完全问题，对最大团问题的研究具有很大的理论价值。 最大团问题也被称为最大独立集问题，在实践中有非常广泛的应用，被应用于市场分析、方案选择、信号传输、计算机视觉、故障诊断、人工智能、聚类分析、移动计算等不同领域。,MCP回溯法详细介绍,概念补充,如果UV且对任意u，vU有(u，v)E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。 对于任一无向图G=(V，E)其补图G=(V1，E1)定义