12

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

版本 1

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

输出：如果存在子图则为真，否则为假

算法（在类似 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

输入：大小为 n x n 的邻接矩阵，k 是要查找的子图的大小

输出：大小为 k 的 A 中的所有完整子图。

算法（这次是函数式/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的 clique 的大小

输出：如果集团确实存在则为真，否则为假

算法：

  1. 求笛卡尔积 V k。
  2. 对于结果中的每个元组，测试每个顶点是否相互连接。如果全部连接，则返回 true 并退出。
  3. 返回 false 并退出。

更新：添加了第二个版本。我认为这正在变得更好，尽管我没有添加任何花哨的动态编程（我知道）。

更新 2：添加了更多评论和文档以使第 2 版更具可读性。这可能是我今天上交的版本。感谢大家的帮助！我希望我能接受多个答案，但我接受了对我帮助最大的人的答案。我会让你们知道我的教授的想法。

4

4 回答 4

8

一些评论：

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

我曾经实现了一种算法来查找图中的所有最大团，这与您的问题类似。我这样做的方式是基于这篇论文：http ://portal.acm.org/citation.cfm?doid=362342.362367 - 它描述了一个回溯解决方案，我发现它作为指南非常有用，尽管我从那张纸。你需要订阅才能获得，但我想你的大学会有一个可用的。

不过，关于那篇论文的一件事是，我真的认为他们应该将“未设置”命名为“已经考虑设置”，因为否则它太令人困惑了。

于 2009-02-04T02:39:54.173 回答
2

算法“对于每个顶点的 k 元组，如果它是一个团，则返回 true”肯定有效。然而，它是蛮力，这可能不是算法课程所要寻找的。相反，请考虑以下事项：

  1. 每个顶点都是一个 1-clique。
  2. 对于每个 1-clique，连接到 1-clique 中的顶点的每个顶点都有助于 2-clique。
  3. 对于每个 2-clique，连接到 2-clique 中每个顶点的每个顶点都有助于 3-clique。
  4. ...
  5. 对于每个 (k-1)-clique，连接到 (k-1) clique 中每个顶点的每个顶点都对 k-clique 有贡献。

这个想法可能会导致更好的方法。

于 2009-02-04T02:48:47.430 回答
0

令人惊讶的是，将内容作为问题输入会向您展示您刚刚写的内容。这一行：

P = A x A x A  //Cartesian product

应该是这样的：

P = A k //笛卡尔积

A^k 是什么意思？您正在服用矩阵产品吗？如果是这样，A 是邻接矩阵吗（你说它是 n+1 个元素的数组）？

在 setbuilder 表示法中，它看起来像这样：

P = {(x0, x1, ... xk) | x0 ∈ A 和 x1 ∈ A ...和 ​​xk ∈ A}

它基本上只是 A 的笛卡尔积 k 次。在纸上，我把它写成 k 是 A 的上标（我刚刚想出了如何使用降价来做到这一点）。

另外，A 只是每个单独顶点的数组，不考虑邻接。

于 2009-02-04T02:03:57.490 回答