我的天真最大集团发现算法比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执行时间,但还不足以超越我的初始解决方案.这种情况似乎是错误的; 我错过了什么算法见解？这里是一个书面记录更多的细节,如果你需要看到完整的工作代码.我已经在伪随机集上测试了这个,其大小达到了一百万左右.

Answer 1

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

max-clique 问题是一个众所周知的 NP 难题，并且两种算法（朴素算法和 Bron Kerbosch 算法）具有相同的复杂度，因此我们不能期望对所有测试用例进行全局改进，而只是对某些特定情况进行改进。但由于您使用均匀分布来生成图表，因此不会出现这种特殊情况。

这就是为什么两种算法在数据上的性能非常相似。而且由于 Bron Kerbosch 算法比朴素算法稍微复杂一些，因此朴素算法速度更快。