Clique问题算法设计

Question

我的算法类中的一个任务是设计一个穷举搜索算法来解决集团问题.也就是说,给定大小为n的图,该算法应该确定是否存在大小为k的完整子图.我想我已经得到了答案,但我不禁想到它可以改进.这就是我所拥有的:

版本1

输入:由数组A [0,... n -1] 表示的图形,要查找的子图形的大小k.

output:如果子图存在则为True,否则为False

算法(类似python的伪代码):

def clique(A, k):
    P = A x A x A //Cartesian product
    for tuple in P:
        if connected(tuple):
            return true
    return false

def connected(tuple):
    unconnected = tuple
    for vertex in tuple:
        for test_vertex in unconnected:
            if vertex is linked to test_vertex:
                remove test_vertex from unconnected
    if unconnected is empty:
        return true
    else:
        return false

版本2

input:大小为n乘n的邻接矩阵,k是要查找的子图的大小

输出:A中大小为k的所有完整子图.

算法(这次是在函数/ Python伪代码中):

//Base case:  return all vertices in a list since each
//one is a 1-clique
def clique(A, 1):
    S = new list
    for i in range(0 to n-1):
        add i to S
    return S

//Get a tuple representing all the cliques where
//k = k - 1, then find any cliques for k
def clique(A,k):
    C = clique(A, k-1)
    S = new list
    for tuple in C:
        for i in range(0 to n-1):
            //make sure the ith vertex is linked to each
            //vertex in tuple
            for j in tuple:
                if A[i,j] != 1:
                    break
            //This means that vertex i makes a clique
            if j is the last element:
                newtuple = (i | tuple) //make a new tuple with i added
                add newtuple to S
    //Return the list of k-cliques
    return S

有没有人有任何想法,意见或建议？这包括我可能错过的错误以及使其更具可读性的方法(我不习惯使用很多伪代码).

版本3

幸运的是,我在提交任务之前与我的教授交谈过.当我发现他的伪代码,我写了,他笑着对我说,我做了这样的工作太多了.首先,我没有提交伪代码; 我只需证明我理解了这个问题.其二,他是想蛮力解决方案.所以我上交的内容看起来像这样:

输入:图G =(V,E),找到k的集团的大小

output:如果clique确实存在则为True,否则为false

算法:

1. 找到笛卡儿积V ^k.
2. 对于结果中的每个元组,测试每个顶点是否彼此连接.如果全部已连接,则返回true并退出.
3. 返回false并退出.

更新:添加第二个版本.虽然我没有添加任何花哨的动态编程(我知道),但我认为这会越来越好.

更新2:添加了一些注释和文档,使版本2更具可读性.这可能是我今天转的版本.谢谢大家的帮助!我希望我能接受不止一个答案,但我接受了最能帮助我的人的答案.我会让你们知道我的教授的想法.

Answer 1

一些评论:

• 您只需要考虑n-choose-k顶点组合,而不是所有k元组(n ^ k).
• connected(tuple)看起来不对劲.你不需要unconnected在循环内重置吗？
• 正如其他人所建议的那样,有更好的方法可以强制执行此操作.考虑以下递归关系:如果前k个顶点形成一个clique并且顶点(k + 1)与每个前k个顶点相邻,则A(k + 1) - 子图是一个集团.您可以在两个方向上应用此方法:
  • 从1-clique开始,逐渐扩大集团,直到你得到所需的大小.例如,如果m是当前clique中的最大顶点,请尝试添加顶点{m + 1,m + 2,...,n-1}以获得一个顶点更大的clique.(这类似于深度优先树遍历,其中树节点的子节点是大于当前集团中最大顶点的顶点.)
  • 从所需大小的子图开始,并使用递归关系检查它是否是一个集团.设置一个memoization表来存储结果.
• (实现建议)使用邻接矩阵(0-1)表示图中的边.
• (初始修剪)丢弃程度小于k的所有顶点.