क्या कोई मुझे बता सकता है, वेब पर जहां मैं ब्रिक-केर्बोश एल्गोरिदम के लिए स्पष्टीकरण ढूंढ सकता हूं या यहां व्याख्या करता हूं कि यह कैसे काम करता है?क्लोन खोज के लिए ब्रोन-केर्बोश एल्गोरिदम
मुझे पता है कि यह "एल्गोरिदम 457: एक अप्रत्यक्ष ग्राफ की सभी वस्तुओं को ढूंढने" पुस्तक में प्रकाशित हुआ था, लेकिन मुझे मुक्त स्रोत नहीं मिल रहा है जो एल्गोरिदम का वर्णन करेगा।
मुझे एल्गोरिदम के लिए स्रोत कोड की आवश्यकता नहीं है, मुझे यह बताता है कि यह कैसे काम करता है।
एक एसीएम छात्र खाते के साथ कोई है जो आप कागज है, जो यहाँ है की एक प्रति दे सकते हैं खोजने का प्रयास करें: http://portal.acm.org/citation.cfm?doid=362342.362367
मैं बस इसे डाउनलोड किया है, और यह केवल दो पृष्ठों लंबा है, अल्गोल 60 में एक कार्यान्वयन के साथ! http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup
HTH:
क्या आप कृपया मुझे [email protected] पर भेजें? –
क्या इसके लायक है के लिए, मैं एक जावा कार्यान्वयन पाया।
मुझे 2 जावा कार्यान्वयन और एक सी कार्यान्वयन मिला। यह काम करता है, लेकिन मुझे यह समझने की भी आवश्यकता है कि यह कैसे काम करता है, और स्रोत कोड में इस बारे में बहुत सारी टिप्पणियां नहीं हैं कि यह कैसे काम करता है। –
वहाँ एल्गोरिथ्म सही here मैं जावा linkedlists का उपयोग कर इसे फिर से लिखा है के रूप में सेट आर, पी, एक्स और यह एक आकर्षण की तरह काम करता है (है ओ अच्छी बात जब आपरेशन सेट कर के अनुसार समारोह "retainAll" का उपयोग करने के लिए है एल्गोरिदम)।
मेरा सुझाव है जब एल्गोरिथ्म
पुनर्लेखन आप अनुकूलन समस्याओं के कारण कार्यान्वयन के बारे में एक छोटे से लगता है कि मैं एल्गोरिथ्म यहाँ की व्याख्या पढ़ सकते हैं: http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf यह एक अच्छा व्याख्या दी गई है ... लेकिन मैं एक पुस्तकालय की जरूरत है या सी # -.- '
में कार्यान्वयन मैंने पेपर में निर्दिष्ट दोनों संस्करणों को लागू किया है। मैंने सीखा कि, अप्रत्याशित संस्करण, अगर हल किया गया है तो एल्गोरिदम को समझने में बहुत मदद करता है। यहाँ संस्करण 1 (unoptimized) के लिए अजगर दिया गया है:
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 पाया क्लिक्स शामिल होंगे।
एक बार जब आप इसे समझ लें तो इसे अनुकूलित करने में आसान है।
एल्गोरिदम जांच का संस्करण 1 भी नहीं होना चाहिए यदि कोई तत्व नहीं है जो अभ्यर्थियों में हर तत्व का पड़ोसी है और बैकट्रैक यदि ऐसा है तो? –
बूस्ट :: ग्राफ में ब्रॉन-केर्बोश एल्गोरिदम का उत्कृष्ट कार्यान्वयन है, इसे चेक दें।
मैं भी ब्रोन-केर्बोश एल्गोरिदम के चारों ओर अपने सिर को लपेटने की कोशिश कर रहा था, इसलिए मैंने अजगर में अपना स्वयं का कार्यान्वयन लिखा। इसमें एक टेस्ट केस और कुछ टिप्पणियां शामिल हैं। उम्मीद है की यह मदद करेगा।
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)
एलेक्स मैं शर्त लगाता हूं कि पोस्ट "मुझे बताएं, वेब पर कहां ..." लोगों को नौकरी करने के लिए मत कहें। बस उन्हें यह स्पष्ट करने के लिए कहें कि यह – aku
का काम कैसे करता है, जैसा कि पुस्तक में नहीं है, क्योंकि मेरे पास पुस्तक में नहीं है, क्योंकि मेरे पास लगभग दो सप्ताह तक लाइब्रेरी तक पहुंच नहीं है :( –
एक स्रोत मांगने के बजाय, बेहतर कहने के लिए " मैं कैसे काम करता हूं ... विशेष रूप से आपको परेशान करने के विवरण के साथ, फिर उत्तर (और आपके प्रश्न का संदर्भ) भविष्य में इसका सामना करने वाले अन्य लोगों के लिए यहां होगा। स्वीकार्य उत्तर यहां बेकार है। – SimonJ