एल्गोरिदम पूर्णांक के दो सेटों के भीतर सबसेट ढूंढने के लिए जिनकी रकम

Question

से मेल खाती है, मैं एक एल्गोरिदम खोज रहा हूं जो पूर्णांक के दो सेट (सकारात्मक और नकारात्मक दोनों) ले सकता है और प्रत्येक के भीतर सबसेट ढूंढ सकता है।

समस्या subset sum problem के समान है सिवाय इसके कि मैं दोनों तरफ से सबसेट ढूंढ रहा हूं।

यहाँ एक उदाहरण है:

लिस्ट ए {4, 5, 9, 10, 1}

सूची B {21, 7, -4, 180}

तो केवल मैच यहां है: {10, 1, 4, 9} < => {21, 7, -4}

क्या किसी को पता है कि इस तरह की समस्याओं के लिए मौजूदा एल्गोरिदम हैं या नहीं?

अब तक एकमात्र समाधान मैं एक जानवर बल दृष्टिकोण है जो हर संयोजन की कोशिश करता है, लेकिन यह घातीय समय में करता है और मैं तत्वों की संख्या पर एक हार्ड सीमा डाल करने के लिए भी लेने से यह से बचने के लिए विचार करने के लिए मिला है लंबा।

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

Answer 1

क्या अन्य लोगों ने कहा सत्य है:

1. यह समस्या एनपी पूरा हो गया है। सामान्य सबसेट-योग के लिए एक आसान कमी है। आप यह नोट करके यह दिखा सकते हैं कि ए के एक उप-समूह को बी (दोनों खाली नहीं) केवल एक यूनियन (-बी) का एक गैर-खाली सबसेट शून्य पर है।

2. यह समस्या, केवल कमजोर एनपी पूरा हो गया है कि यह संख्या शामिल के आकार में बहुपद है, लेकिन उनके लघुगणक में घातीय होने की अनुमान लगाया जाता है। इसका मतलब है कि मोनिकर "एनपी-पूर्ण" की तुलना में समस्या आसान है।

3. आपको गतिशील प्रोग्रामिंग का उपयोग करना चाहिए।

तो क्या मैं इस चर्चा के लिए योगदान दे रहा हूँ? खैर, (पर्ल में) कोड:

@a = qw(4 5 9 10 1); 
@b = qw(21 7 -4 180); 
%a = sums(@a); 
%b = sums(@b); 
for $m (keys %a) { 
    next unless exists $b{$m}; 
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0); 
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n"; 
} 

sub sums { 
    my(@a) = @_; 
    my($a, %a, %b); 
    %a = (0 => []); 
    while(@a) { 
     %b = %a; 
     $a = shift @a; 
     for my $m (keys %a) { 
      $b{$m+$a} = [@{$a{$m}},$a]; 
     } 
    %a = %b; 
    } 
    return %a; 
} 

यह प्रिंट

sum(4 5 9 10) = sum(21 7) 
sum(4 9 10 1) = sum(21 7 -4) 

हां, विशेष रूप से, वहाँ एक से अधिक समाधान है कि अपने मूल समस्या में काम करता है!

संपादित करें: उपयोगकर्ता इज़ी ने सही ढंग से बताया कि यह समाधान गलत तरीके से गलत था, और बदतर, कई तरीकों से !! मुझे इसके बारे में बहुत खेद है और मैंने उम्मीद है कि उपरोक्त नए कोड में इन चिंताओं को संबोधित किया है। फिर भी, अभी भी एक समस्या है, अर्थात् किसी भी विशेष सबसेट के लिए, यह केवल संभावित समाधानों में से एक प्रिंट करता है। पिछली समस्याओं के विपरीत, जो सीधे त्रुटियां थीं, मैं इसे एक जानबूझकर सीमा के रूप में वर्गीकृत करूंगा। शुभकामनाएँ और बग से सावधान रहें!

Answer 2

सबसेट योग एनपी-पूर्ण है और आप अपनी समस्या को बहुपद रूप से कम कर सकते हैं, इसलिए आपकी समस्या एनपी-पूर्ण भी है।

Answer 3

सबसेट योग समस्या की तरह, यह समस्या कमजोर एनपी-पूर्ण है, इसलिए इसमें एक समाधान है जो समय बहुपद (एम) में चलता है, जहां एम समस्या उदाहरण में दिखाई देने वाली सभी संख्याओं का योग है। आप गतिशील प्रोग्रामिंग के साथ इसे प्राप्त कर सकते हैं। प्रत्येक सेट के लिए आप 2-आयामी द्विआधारी तालिका भरकर सभी संभावित रकम उत्पन्न कर सकते हैं, जहां (के, एम) पर "सत्य" का अर्थ है कि सेट के पहले के तत्वों से कुछ तत्व चुनकर एक सबसेट योग मीटर प्राप्त किया जा सकता है।

आप इसे iteratively भरने - आप (के, मी) "सही" (k-1, मी) सेट है, तो करने के लिए "सही" (जाहिर है, अगर आप कश्मीर -1 तत्वों से मीटर प्राप्त कर सकते हैं, आप कर सकते हैं सेट के-वें नहीं चुनकर इसे के तत्वों से प्राप्त करें) या यदि (के -1, एमडी) "सत्य" पर सेट है जहां डी सेट में के-वें तत्व का मान है (जिस मामले में आप के- वें तत्व)।

तालिका भरना आपको अंतिम कॉलम (पूरे सेट का प्रतिनिधित्व करने वाला) में सभी संभावित रकम प्राप्त करता है। दोनों सेटों के लिए ऐसा करें और सामान्य रकम खोजें। आप उन प्रक्रियाओं को उलट कर समाधानों का प्रतिनिधित्व करने वाले वास्तविक सबसेट को बैकट्रैक कर सकते हैं जिन्हें आपने टेबल भरने के लिए उपयोग किया था।

Answer 4

सभी त्वरित प्रतिक्रियाओं के लिए बहुत बहुत धन्यवाद!

गतिशील प्रोग्रामिंग समाधान हमारे पास अभी तक मौजूद संपूर्ण दृष्टिकोण के लिए वास्तव में अलग नहीं है और मुझे लगता है कि अगर हमें इष्टतम समाधान की आवश्यकता है तो हमें हर संभव संयोजन पर विचार करने की आवश्यकता है, लेकिन रकम की इस संपूर्ण सूची को उत्पन्न करने में लगने वाला समय

11 elements took - 0.015625 seconds 
12 elements took - 0.015625 seconds 
13 elements took - 0.046875 seconds 
14 elements took - 0.109375 seconds 
15 elements took - 0.171875 seconds 
16 elements took - 0.359375 seconds 
17 elements took - 0.765625 seconds 
18 elements took - 1.609375 seconds 
19 elements took - 3.40625 seconds 
20 elements took - 7.15625 seconds 
21 elements took - 14.96875 seconds 
22 elements took - 31.40625 seconds 
23 elements took - 65.875 seconds 
24 elements took - 135.953125 seconds 
25 elements took - 282.015625 seconds 
26 elements took - 586.140625 seconds 
27 elements took - 1250.421875 seconds 
28 elements took - 2552.53125 seconds 
29 elements took - 5264.34375 seconds 

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

धन्यवाद सब वही!