ruby - 我天真的最大团发现算法比 Bron-Kerbosch 的运行得更快。怎么了？

Question

简而言之，我的原始代码(用 Ruby 编写)如下所示:

# $seen is a hash to memoize previously seen sets
# $sparse is a hash of usernames to a list of neighboring usernames
# $set is the list of output clusters

$seen = {}
def subgraph(set, adj)
    hash = (set + adj).sort
    return if $seen[hash]
    $sets.push set.sort.join(", ") if adj.empty? and set.size > 2
    adj.each {|node| subgraph(set + [node], $sparse[node] & adj)}
    $seen[hash] = true
end

$sparse.keys.each do |vertex|
    subgraph([vertex], $sparse[vertex])
end

还有我的 Bron Kerbosch 实现:

def bron_kerbosch(set, points, exclude)
    $sets.push set.sort.join(', ') if set.size > 2 and exclude.empty? and points.empty?
    points.each_with_index do |vertex, i|
        points[i] = nil
        bron_kerbosch(set + [vertex],
                      points & $sparse[vertex],
                      exclude & $sparse[vertex])
        exclude.push vertex
    end
end

bron_kerbosch [], $sparse.keys, []

我还实现了旋转和退化排序，这减少了 bron_kerbosch 的执行时间，但不足以超过我最初的解决方案。这种情况似乎是错误的；我缺少什么算法洞察力？这是一个 writeup如果您需要查看完整的工作代码，请提供更多详细信息。我已经在大小为一百万左右的边的伪随机集上对此进行了测试。

Answer 1

我不知道你是如何为你的测试生成随机图的，但我想你使用了一个根据均匀分布生成数字的函数，因此你获得了一个非常均匀的图。这是在图上测试算法时的常见问题，创建好的测试用例非常困难(通常与解决原始问题一样困难)。

max-clique 问题是一个众所周知的 NP 难题，两种算法(朴素算法和 Bron Kerbosch 算法)具有相同的复杂度，因此我们不能期望对所有测试用例进行全局改进，而只是对一些特殊情况。但是因为您使用了均匀分布来生成图形，所以您没有这种特殊情况。

这就是为什么这两种算法在您的数据上的表现非常相似。而且因为 Bron Kerbosch 算法比朴素算法稍微复杂一点，所以朴素算法更快。