题

我的算法课上的作业之一是设计一种穷举搜索算法来解决派系问题。也就是说，给定尺寸图 n, ，该算法应该确定是否存在尺寸的完整子图 k. 。我想我已经得到了答案，但我忍不住认为它可以改进。这是我所拥有的：

版本1

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

输出:如果子图存在则为 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

输入:大小为 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

输出:如果派系确实存在则为 true，否则为 false

算法:

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

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

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

有帮助吗？

解决方案

一些评论：

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

其他提示

我曾经实现了一种算法来查找图中的所有最大派系，这与您的问题类似。我的做法是基于这篇论文： http://portal.acm.org/itation.cfm?doid=362342.362367 - 它描述了一个回溯解决方案，我发现它作为指南非常有用，尽管我对该论文进行了很多修改。不过，您需要订阅才能获得此服务，但我想您的大学应该有订阅服务。

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

“对于每个 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 有贡献。

这个想法可能会带来更好的方法。

也许尝试一下 动态规划技术.

令人惊奇的是，将内容作为问题写下来会告诉你刚刚写的内容。这行：

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 的上标（我现在才知道如何使用 markdown 来做到这一点）。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top