خوارزمية برون-كربوش لإيجاد الزمرة

StackOverflow https://stackoverflow.com/questions/143140

  •  02-07-2019
  •  | 
  •  

سؤال

هل يمكن لأحد أن يخبرني، أين يمكنني العثور على شرح على الويب لخوارزمية Bron-Kerbosch لإيجاد الزمرة أو شرح كيفية عملها هنا؟

أعلم أنه تم نشره في "الخوارزمية 457:"العثور على جميع مجموعات الرسم البياني غير الموجه"، لكن لا يمكنني العثور على مصدر مجاني يصف الخوارزمية.

لا أحتاج إلى كود مصدر للخوارزمية، أحتاج إلى شرح لكيفية عملها.

هل كانت مفيدة؟

المحلول

حاول العثور على شخص لديه حساب طالب في ACM يمكنه إعطاؤك نسخة من الورقة، الموجودة هنا: http://portal.acm.org/citizen.cfm?doid=362342.362367

لقد قمت بتنزيله للتو، وهو مكون من صفحتين فقط، مع تنفيذ في Algol 60!

نصائح أخرى

أجد شرح الخوارزمية هنا: http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdfإنه تفسير جيد...لكنني بحاجة إلى مكتبة أو تطبيق في C# -.-'

هناك الخوارزمية الصحيحة هنا لقد قمت بإعادة كتابتها باستخدام قوائم Java Linkedlists حيث أن المجموعات R ، P ، X ، وهي تعمل مثل السحر (يا شيء جيد هو استخدام الوظيفة "الاحتفاظ" عند القيام بعمليات تعيين وفقًا للخوارزمية).

أقترح عليك التفكير قليلاً في التنفيذ بسبب مشكلات التحسين عند إعادة كتابة الخوارزمية

كنت أحاول أيضًا أن ألتف حول خوارزمية برون-كربوش، لذلك كتبت تطبيقي الخاص في بايثون.ويتضمن حالة اختبار وبعض التعليقات.أتمنى أن يساعدك هذا.

class Node(object):

    def __init__(self, name):
        self.name = name
        self.neighbors = []

    def __repr__(self):
        return self.name

A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')

A.neighbors = [B, C]
B.neighbors = [A, C]
C.neighbors = [A, B, D]
D.neighbors = [C, E]
E.neighbors = [D]

all_nodes = [A, B, C, D, E]

def find_cliques(potential_clique=[], remaining_nodes=[], skip_nodes=[], depth=0):

    # To understand the flow better, uncomment this:
    # print (' ' * depth), 'potential_clique:', potential_clique, 'remaining_nodes:', remaining_nodes, 'skip_nodes:', skip_nodes

    if len(remaining_nodes) == 0 and len(skip_nodes) == 0:
        print 'This is a clique:', potential_clique
        return

    for node in remaining_nodes:

        # Try adding the node to the current potential_clique to see if we can make it work.
        new_potential_clique = potential_clique + [node]
        new_remaining_nodes = [n for n in remaining_nodes if n in node.neighbors]
        new_skip_list = [n for n in skip_nodes if n in node.neighbors]
        find_cliques(new_potential_clique, new_remaining_nodes, new_skip_list, depth + 1)

        # We're done considering this node.  If there was a way to form a clique with it, we
        # already discovered its maximal clique in the recursive call above.  So, go ahead
        # and remove it from the list of remaining nodes and add it to the skip list.
        remaining_nodes.remove(node)
        skip_nodes.append(node)

find_cliques(remaining_nodes=all_nodes)

لقد قمت بتنفيذ كلا الإصدارين المحدد في الورقة.تعلمت أن النسخة غير المحسنة، إذا تم حلها بشكل متكرر، تساعد كثيرًا في فهم الخوارزمية.فيما يلي تطبيق python للإصدار 1 (غير محسّن):

def bron(compsub, _not, candidates, graph, cliques):
    if len(candidates) == 0 and len(_not) == 0:
        cliques.append(tuple(compsub))
        return
    if len(candidates) == 0: return
    sel = candidates[0]
    candidates.remove(sel)
    newCandidates = removeDisconnected(candidates, sel, graph)
    newNot = removeDisconnected(_not, sel, graph)
    compsub.append(sel)
    bron(compsub, newNot, newCandidates, graph, cliques)
    compsub.remove(sel)
    _not.append(sel)
    bron(compsub, _not, candidates, graph, cliques)

وقمت باستدعاء هذه الوظيفة:

graph = # 2x2 boolean matrix
cliques = []
bron([], [], graph, cliques)

المتغير cliques سوف تحتوي على مجموعات تم العثور عليها.

بمجرد أن تفهم هذا، سيكون من السهل تنفيذ الحل الأمثل.

Boost::Graph لديه تطبيق ممتاز لخوارزمية Bron-Kerbosh، قم بتجربته.

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top