Мой наивный алгоритм поиска максимальной клики работает быстрее, чем алгоритм Брон-Кербоша.В чем дело? - PullRequest
Новая
       41

Мой наивный алгоритм поиска максимальной клики работает быстрее, чем алгоритм Брон-Кербоша.В чем дело?

7 голосов
/ 01 марта 2011

Короче, мой наивный код (на 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, но не настолько, чтобы обогнать мое первоначальное решение. Кажется неправильным, что это так; Какое алгоритмическое понимание мне не хватает? Вот запись с более подробной информацией, если вам нужно увидеть полностью рабочий код. Я проверял это на псевдослучайных наборах размером до миллиона ребер.

1 Ответ

3 голосов
/ 24 мая 2012

Я не знаю, как вы генерируете случайные графики для своих тестов, но я полагаю, что вы используете функцию, которая генерирует число в соответствии с равномерным распределением, и, таким образом, вы получаете график, который является очень однородным.Это общая проблема при тестировании алгоритмов на графиках, очень трудно создавать хорошие тестовые случаи (это часто так же сложно, как решить исходную проблему).

Проблема max-clique - это хорошо известная трудная проблема NPи оба алгоритма (наивный и Bron Kerbosch) имеют одинаковую сложность, поэтому мы не можем ожидать глобального улучшения во всех тестах, а просто улучшения в некоторых конкретных случаях.Но поскольку вы использовали равномерное распределение для генерации вашего графика, у вас нет этого конкретного случая.

Именно поэтому производительность обоих алгоритмов очень схожа с вашими данными.А поскольку алгоритм Брон Кербоша немного сложнее, чем наивный, наивный быстрее.

...