我天真的最大派系查找算法比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 

我的布龙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算法比天真的算法复杂一点，天真的算法更快。