最大团问题算法的改进

最大团问题算法的改进

简介

 最大团问题（Maximum Clique Problem, MCP）是图论中一个经典的组合优化问题，也是一类NP完全问题，在国际上已有广泛的研究，而国内对MCP问题的研究则还处于起步阶段，因此，研究最大团问题具有较高的理论价值和现实意义。

 给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果U V，且对任意两个顶点u，v∈U有(u,v)∈E，则称U是G的完全子图。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’的最大独立集。
通俗点讲就是在一个无向图中找出一个点数最多的完全图。

改进思路

 定义Si={vi,vi+1,…,vn}，按照Sn,Sn-1,…,S1的顺序求解。从 而得到一个更精确的上界函数，若currSize+solution[Si]<=max则 剪枝。同时注意到：从Si+1到Si，如果找到一个更 大的团，那么vi必然属于找到的团，此时有 Si=Si+1+1，否则Si=Si+1。因此只要max的值被更新过， 就可以确定已经找到最大值，不必再往下搜索了
伪代码(原作者:Patric R. J. Ostergard)

具体java代码如下:

/** Copyright (c) 2019 Ng Kimbing, HNU, All rights reserved. May not be used, modified, or copied without permission.* @Author: Ng Kimbing, HNU.* @LastModified:2019-05-12 T 16:02:57.411 +08:00*/
package ACMProblems.BackTrack;import java.util.*;import static ACMProblems.ACMIO.*;public class MaxCliqueProblem {private static int max = 0;private static boolean found = false;private static boolean matrix[][] = new boolean[100][100];private static int[] sol = new int[100];private static int v;private static Set<Integer> removed = new HashSet<>();private static void addEdge(int a, int b) {matrix[a][b] = true;matrix[b][a] = true;}private static boolean hasEdge(int a, int b) {return matrix[a][b];}/*** Delete the vertices in the collection that are not connected to point i.** @param set the set* @param i   vertex i*/private static void removeUnrelatedVertex(Set<Integer> set, int i) {Iterator<Integer> it = set.iterator();removed.clear();while (it.hasNext()) {int temp = it.next();if (!hasEdge(i, temp)) {it.remove();removed.add(temp);}}}/*** By constantly reducing the elements in the collection, the size is constantly increasing, updating the max value** @param set  current set* @param size current size*/private static void clique(Set<Integer> set, int size) {if (set.isEmpty()) {if (size > max) {max = size;found = true;}return;}while (!set.isEmpty()) {//pruneif (size + set.size() <= max)return;Iterator<Integer> it = set.iterator();int i = it.next();//pruneif (size + sol[i] <= max)return;//i-th vertex is in the ve(i);// if the max clique contains i,// vertexes that are not connect to i won't be in the max cliqueremoveUnrelatedVertex(set, i);// assume that max clique contains i, so we have size+1clique(set, size + 1);if (found)return;// backtrack. max clique doesn't contain i, size doesn't change.set.addAll(removed);}}/*** get a set which contains [i,v]** @param i start* @return the set*/private static Set<Integer> getS(int i) {Set<Integer> set = new TreeSet<>();for (; i <= v; ++i)set.add(i);return set;}/*** solveWithResult MCP** @return return max clique number*/private static int solve() {for (int i = v; i > 0; --i) {found = false;Set<Integer> si = getS(i);removeUnrelatedVertex(si, i);//After calling this function,  max = max + 1 or max = maxclique(si, 1);sol[i] = max;}return max;}public static void main(String[] args) throws Exception {setStream(System.in);v = nextInt();int e = nextInt();for (int i = 0; i < e; ++i) {int from, to;from = nextInt();to = nextInt();addEdge(from, to);}System.out.println(solve());}
}