0037算法笔记——【分支限界法】最大团问题程序.docx

问题描述??? ?给定无向图G=(V, E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果U∈V，且对任意两个顶点u，v∈U有(u, v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。? ? ?如果U∈V且对任意u，v∈U有(u, v)不属于E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。? ? ?对于任一无向图G=(V, E)，其补图G=(V, E)定义为：V=V，且(u, v)∈E当且仅当(u, v)∈E。? ? ?如果U是G的完全子图，则它也是G的空子图，反之亦然。因此，G的团与G的独立集之间存在一一对应的关系。特殊地，U是G的最大团当且仅当U是G的最大独立集。? ? ?例：如图所示，给定无向图G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根据最大团(MCP)定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。{1,2,5}是G的一个最大团。{1,4,5}和{2,3,5}也是G的最大团。右侧图是无向图G的补图G。根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集。虽然{1,2}也是G的空子图，但它不是G的独立集，因为它包含在G的空子图{1,2,5}中。{1,2,5}是G的最大独立集。{1,4,5}和{2,3,5}也是G的最大独立集。? ? ?算法设计? ? ??最大团问题的解空间树也是一棵子集树。子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。?算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。? ? ?接着继续考察当前扩展结点的右儿子结点。当upperSizebestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。? ? 对于子集树中的叶结点，有upperSize＝cliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步有哪些信誉好的足球投注网站不可能得到更大的团，此时算法已找到一个最优解。? ? ?算法具体实现如下：? ? ?1、MaxHeap.h[cpp]?view plain?copytemplateclass?T??class?MaxHeap??{??????public:??????????MaxHeap(int?MaxHeapSize?=?10);??????????~MaxHeap()?{delete?[]?heap;}??????????int?Size()?const?{return?CurrentSize;}????????????T?Max()???????????{??????????//查?????????????if?(CurrentSize?==?0)?????????????{??????????????????throw?OutOfBounds();?????????????}?????????????return?heap[1];??????????}????????????MaxHeapT?Insert(const?T?x);?//增??????????MaxHeapT?DeleteMax(T?x);???//删????????????void?Initialize(T?a[],?int?size,?int?ArraySize);????????private:??????????int?CurrentSize,?MaxSize;??????????T?*heap;??//?element?array??};????templateclass?T??MaxHeapT::MaxHeap(int?MaxHeapSize)??{//?Max?heap?constructor.??????MaxSize?=?MaxHeapSize;??????heap?=?new?T[MaxS