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 の実行時間が短縮されましたが、最初のソリューションを追い越すには十分ではありませんでした。これが事実であるというのは間違っているようです。私が見逃しているアルゴリズムの洞察は何ですか？完全に機能するコードを確認する必要がある場合は、ここに詳細が記載された記事があります。私はこれを疑似ランダム セットで最大 100 万個程度のサイズのエッジでテストしました。

4

1 に答える 1

4

テスト用のランダムグラフをどのように生成するかはわかりませんが、一様分布に従って数値を生成する関数を使用すると、非常に均一なグラフが得られると思います。これは、グラフでアルゴリズムをテストする場合の一般的な問題です。適切なテスト ケースを作成するのは非常に困難です (多くの場合、元の問題を解決するのと同じくらい困難です)。

max-clique 問題はよく知られた NP 困難な問題であり、両方のアルゴリズム (単純なものと Bron Kerbosch のもの) は同じ複雑さを持っているため、すべてのテストケースで全体的な改善を期待することはできませんが、いくつかの特定のケースで改善するだけです。 . しかし、一様分布を使用してグラフを生成したため、この特定のケースはありません。

そのため、データに対する両方のアルゴリズムのパフォーマンスが非常に似ています。また、Bron Kerbosch アルゴリズムは単純なアルゴリズムよりも少し複雑であるため、単純なアルゴリズムの方が高速です。

于 2012-05-24T14:21:06.537 に答える