派系问题算法设计

Question

我的算法课上的作业之一是设计一种穷举搜索算法来解决派系问题。 也就是说，给定一个大小为 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

有人有任何想法、评论或建议吗？ 这包括我可能错过的错误以及使其更具可读性的方法（我不习惯使用太多伪代码）。

第三版

幸运的是，我在提交作业之前和我的教授谈过。 当我向他展示我编写的伪代码时，他微笑着告诉我，我做了太多工作。 其一，我不必提交伪代码； 我只需证明我理解这个问题。 第二，他想要暴力解决方案。 所以我提交的内容看起来像这样：

的团的大小

输入：图形 G = (V,E)，找到k 输出 strong>：如果派确实存在，则为 true，否则为 false

算法：

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

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

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

Answer 1

一些评论：

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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 只是每个单独顶点的数组，不考虑邻接关系。