算法设计与分析-分支限界法-最大团问题演示ppt课件.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邻接矩阵案例分析R团结点数：cliqueSize=cs 上届数：upperSize=us 最大团节点数：bestn-bn其中上届数（us）=团节点数+图节点数-层数+1（cs+n-level+1）当usbncs=1,bn=1,us=1+5-2+1=5,usbncs=0,bn=1,us=0+5-2+1=4,usbn1122cs=2,bn=2,us=2+5-3+1=5,usbncs=1,bn=2,us=1+5-3+1=4,usbnus=433cs=2,bn=2,us=2+5-4+1=4,usbn节点1,3不临接，故剪枝us=422cs=1,bn=2,us=1+5-3+1=4,usbncs=0,bn=2,us=0+5-3+1=3,usbnus=433节点1,3不临接，故剪枝cs=1,bn=2,us=1+5-4+1=3,usbnus=4us=344节点2,4不临接，故剪枝cs=2,bn=2,us=2+5-5+1=3,usbnus=333cs=2,bn=2,us=2+5-4+1=4,usbncs=1,bn=2,us=1+5-4+1=3,usbn44节点2,4不临接，故剪枝cs=2,bn=2,us=2+5-5+1=3,usbn33cs=1,bn=2,us=1+5-4+1=3,usbncs=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=244cs=2,bn=2,us=2+5-5+1=3,usbncs=1,bn=2,us=1+5-5+1=2,us=bn左1右2右3左4us=3左1右2右3右4us=255cs=3,bn=3,us=3+5-6+1=3,us=cs 已到叶子结点，此为最优解回溯法分支限界法求解目标找出解空间树中满足约束条件的所有解。找出满足约束条件的一个解，或是在满足约束条件的解中找出满足某种意义的最优解。搜索方式以深度优先的方式搜索解空间树。以广度优先或以最小耗费优先的方式搜索空间。算法复杂度O(n2n)O(n2n)访问节点数平均情况下多平均情况下少分支限界法与回溯法对比算法实现运行程序C+实现谢谢 谢！谢！放映结束 感谢各位的批评指导！让我们共同进步
