简而言之,我的简单代码(用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。我已经在大约一百万条边的伪随机集上测试了这一点。
发布于 2012-05-24 22:21:07
我不知道你是如何为你的测试生成随机图的,但我假设你使用了一个函数,它根据均匀分布生成一个数字,因此你得到了一个非常均匀的图。在图上测试算法时,这是一个常见的问题,很难创建好的测试用例(通常与解决原始问题一样困难)。
最大团问题是一个众所周知的NP难题,两种算法(朴素算法和Bron Kerbosch算法)都有相同的复杂度,所以我们不能期望在所有测试用例上都有全局改进,而只是在某些特定情况下有所改进。但是因为您使用了均匀分布来生成图形,所以没有这种特殊的情况。
这就是为什么两种算法在您的数据上的性能非常相似的原因。因为Bron Kerbosch算法比朴素的算法稍微复杂一些,所以朴素的算法更快。
https://stackoverflow.com/questions/5149477
复制相似问题