मेरा बेवकूफ अधिकतम क्लिक खोज एल्गोरिदम ब्रॉन-केर्बोश की तुलना में तेज़ी से चलता है। क्या गलत है?

Question

संक्षेप में, मेरी भोली कोड (रूबी में) लगता है कि:

# $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 निष्पादन समय में कटौती , लेकिन मेरे शुरुआती समाधान से आगे निकलने के लिए पर्याप्त नहीं है। ऐसा लगता है कि यह मामला है; मुझे क्या एल्गोरिदमिक अंतर्दृष्टि याद आ रही है? अगर आपको पूरी तरह से काम करने वाला कोड देखना है तो अधिक जानकारी के साथ writeup यहां दिया गया है। मैंने इसे छद्म-यादृच्छिक सेट पर दस लाख या उससे अधिक किनारों पर परीक्षण किया है।

Answer 1

मुझे नहीं पता कि आप अपने परीक्षणों के लिए यादृच्छिक ग्राफ कैसे उत्पन्न करते हैं, लेकिन मुझे लगता है कि आप एक ऐसे फ़ंक्शन का उपयोग करते हैं जो एक समान वितरण के अनुसार संख्या उत्पन्न करता है और इस प्रकार आप एक ग्राफ प्राप्त करते हैं जो बहुत ही सजातीय है। ग्राफ पर एल्गोरिदम का परीक्षण करते समय यह एक आम समस्या है, अच्छे टेस्ट केस बनाना मुश्किल है (यह अक्सर मूल समस्या को हल करने के रूप में कठिन होता है)।

अधिकतम-क्लासिक समस्या एक प्रसिद्ध एनपी हार्ड समस्या है और दोनों एल्गोरिदम (बेवकूफ एक और ब्रॉन केर्बोश एक) में समान जटिलता है इसलिए हम सभी टेस्टकेस पर वैश्विक सुधार की उम्मीद नहीं कर सकते हैं, लेकिन केवल एक सुधार कुछ विशेष मामलों पर। लेकिन चूंकि आपने अपने ग्राफ को उत्पन्न करने के लिए एक समान वितरण का उपयोग किया है, इसलिए आपके पास यह विशेष मामला नहीं है।

यही कारण है कि आपके डेटा पर दोनों एल्गोरिदम का प्रदर्शन बहुत समान है। और क्योंकि ब्रॉन केर्बोश एल्गोरिदम बेवकूफ की तुलना में थोड़ा अधिक जटिल है, बेवकूफ एक तेज़ है।