算法设计与分析-分支限界法-最大团问题.ppt
最大团问题,1.概述2.问题描述3.算法设计4.案例分析5.算法实现,概述,分支限界法 常以广度优先或最小耗费（最大收益）优先的方法搜索问题的解空间树。,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些子结点中，导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中。,以此重复，至活结点不可被加（得到最优解），或活结点为空（无解）。,概述,最大团问题（Maximum Clique Problem，MCP）是图论中一个经典的组合优化问题，也是一类NP完全问题。,最大团问题到底在求什么？,一个无向图的最大完全子图,什么是图的最大完全子图？,就是找一个该图的子图，这个子图中的所有节点都彼此连接。,在上图中：1，2，5和1，4，5，以及2，3，5都是该图的最大完全子图（最大团）1，2是一个完全子图但不是最大完全子图，1，2，3，5不是完全子图，因为1，3不连接。,问题描述,给定无向图 G=V,E，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“()”表示。如果U|V，且对任意两个顶点u,vU有(u,v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。,算法设计,上届函数,用变量cliqueSize表示与该节点相应的团的顶点数；level表示节点在子集空间树中所处的层次；用cliqueSize+n-level+1作为顶点数上届upperSize的值在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。,算法设计,终止条件,1.从根节点R出发，遍历首个节点，计算其团节点数cliqueSize=cs，当前最大团节点数bestn=bn，以及上届函数值upperSize=cs+n-level+1=us，比较us、cs和bn的大小关系。2.当usbn，则该节点的子节点中有可行解；当us=bn，若访问完全部数据，则遍历结束；若访问未完成，则该节点子树中没有可行解。3.比较当前活结点的upperSize值，根据队列优先访问下一个节点。4.循环，直至us=cs，得到最优解。,算法的while循环的终止条件是遇到子集树的一个叶节点（即n+1层节点）成为当前扩展节点。对于子集树中的叶节点，有uppersize=cliqueSize。此时活节点优先队列剩余节点upperSize值均不超过当前扩展节点的upperSize值，从而进一步搜索不可能得到更大的团，而是算法已找到一个最优解。,案例分析,求下图的最大团（最大完全子图）,我们的图可以定义为G=V,E,其中V是点集，E是边集。其中：V=V1,V2,V3,V4,V5E=E1,E2,E3,E4,E5,E6,E7,邻接矩阵,案例分析,团结点数：cliqueSize=cs 上届数：upperSize=us 最大团节点数：bestn-bn其中上届数（us）=团节点数+图节点数-层数+1（cs+n-level+1）当usbn时，左边剪枝，右边可能有解。上层结点与下层结点不连接，则剪枝。,cs=0,bn=0,us=0+5-1+1=5,usbn,cs=1,bn=1,us=1+5-2+1=5,usbn,cs=0,bn=1,us=0+5-2+1=4,usbn,cs=2,bn=2,us=2+5-3+1=5,usbn,cs=1,bn=2,us=1+5-3+1=4,usbn,us=4,cs=2,bn=2,us=2+5-4+1=4,usbn,节点1,3不临接，故剪枝,us=4,cs=1,bn=2,us=1+5-3+1=4,usbn,cs=0,bn=2,us=0+5-3+1=3,usbn,us=4,节点1,3不临接，故剪枝,cs=1,bn=2,us=1+5-4+1=3,usbn,us=4,us=3,节点2,4不临接，故剪枝,cs=2,bn=2,us=2+5-5+1=3,usbn,us=3,cs=2,bn=2,us=2+5-4+1=4,usbn,cs=1,bn=2,us=1+5-4+1=3,usbn,节点2,4不临接，故剪枝,cs=2,bn=2,us=2+5-5+1=3,usbn,cs=1,bn=2,us=1+5-4+1=3,usbn,cs=0,bn=2,us=0+5-4+1=2,us=bn,左1us=5,右1us=4,左1左2us=5,左1右2us=4,左1左2右3us=4,右1左2us=4,右1右2us=3,左1右2右3us=3,左1左2右3右4us=3,右1左2左3us=4,右1左2右3us=3,右1左2左3右4us=3,右1右2左3us=3,右1右2右3us=2,cs=2,bn=2,us=2+5-5+1=3,usbn,cs=1,bn=2,us=1+5-5+1=2,us=bn,左1右2右3左4us=3,左1右2右3右4us=2,cs=3,bn=3,us=3+5-6+1=3,us=cs 已到叶子结点，此为最优解,分支限界法与回溯法对比,算法实现,运行程序C+实现,
