团问题算法设计

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

有没有人有什么想法、评论或建议？这包括我可能错过的错误以及使此更易读的方法（我不习惯使用伪代码）。

版本3

幸运的是，我在提交作业之前与教授交谈了。当我向他展示我写的伪代码时，他微笑着告诉我，我做的功夫实在太多了。首先，我不必提交伪代码；我只需要证明我理解了这个问题。其次，他是想要暴力解决方案的。所以我提交的东西看起来像这样:

输入：一个图G = (V,E)，要查找的最大团的大小k

输出：若存在最大团则返回true，否则返回false

算法：

1. 找到笛卡尔积 V^k。
2. 对于结果中的每个元组，测试每个顶点是否与其他所有顶点相连通。如果全部相连，则返回true并退出。
3. 返回false并退出。

更新：添加了第二个版本。我认为这一版越来越好了，虽然我还没有添加任何花哨的动态编程（至少我不知道）。

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

- Jason Baker

---

你的意思是大小为k的完全子图，对吧？另外，我认为你的伪代码中没有使用k。 - Zach Scrivena

是的，你两个方面都是正确的。 :-) - Jason Baker

@Jason：有n个顶点，即A[1,...,n]？ - Zach Scrivena

Arghhh... 上面写错了。我是指A[0,...,n-1]，虽然A[1,...,n]应该也可以。 - Jason Baker

@Jason：建议：你能否记录一下这两个函数应该做什么？ - Zach Scrivena

Answer 1

以下是一些评论：

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

- Zach Scrivena

Answer 2

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

不过，关于那篇论文的一个问题是，我真的认为他们应该将“未设置”的名称命名为“已考虑的集合”，否则就会太令人困惑了。

- Ray Hidayat

Answer 3

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

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

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

- Rudd

Answer 4

将事情以问题的形式记录下来，你会惊讶地发现自己刚刚写的东西。这一行：

P = A x A x A  //Cartesian product

应该是这样的：

P = A ^k //笛卡尔积

你说的A^k是什么意思？你在进行矩阵乘法吗？如果是这样，A是否是邻接矩阵（你说它是一个由n+1个元素组成的数组）？

用集合构建符号表示，它看起来像这样：

P = {(x0, x1, ... xk) | x0 ∈ A ，x1 ∈ A ... 且 xk ∈ A}

基本上只是将A的笛卡尔积取了k次。我在纸上将其写成了将k作为A的上标（我现在刚才想到如何使用markdown来实现它）。

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

- Jason Baker

---

A^k是什么意思？你是在进行矩阵乘法吗？如果是这样，A是邻接矩阵吗（你说它是一个由n+1个元素组成的数组）？ - Zach Scrivena

我认为A是一个无序节点列表，即1、2、3、...、n。 A^k给出了它们的每个可能长度为k的组合。然后他检查任何给定的组合是否相连，即团。 - Paul

@Zach：正如评论和答案所说，A^k只是笛卡尔积A×A×...×A（k次方）。[它由k元组（u，v，w，...），其中每个元素都在A中]组成。 - ShreevatsaR

谢谢Paul。你说得比我好。:-) 我会把这当作一个提示，可能需要重新考虑一种更易读的方法来完成这个任务。 - Jason Baker

啊，我明白了。所以图中的边在你的代码中并不是显式的，对吧？ - Zach Scrivena