7

简而言之，我的幼稚代码（在 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 的执行时间，但不足以超越我最初的解决方案。情况似乎是错误的；我缺少什么算法洞察力？如果您需要查看完整的工作代码，这里有一个更详细的文章。我已经在大小达到一百万左右的伪随机集上对此进行了测试。

4

1 回答 1

4

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

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

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

于 2012-05-24T14:21:06.537 回答