उपसमुच्चय योग समस्या

उपसमुच्चय योग समस्या (एसएसपी) कंप्यूटर विज्ञान में एक निर्णय समस्या है। इसके सबसे सामान्य सूत्रीकरण में, एक मल्टीसेट है $S$ पूर्णांकों और एक लक्ष्य-योग का $T$, और प्रश्न यह तय करना है कि क्या पूर्णांकों का कोई उपसमुच्चय सटीक रूप से योग करता है $T$. समस्या को एनपी कठिन माना जाता है। इसके अलावा, इसके कुछ प्रतिबंधित संस्करण एनपी-पूर्णता|एनपी-पूर्ण भी हैं, उदाहरण के लिए:

• वह वैरिएंट जिसमें सभी इनपुट सकारात्मक हैं।
• वह प्रकार जिसमें इनपुट सकारात्मक या नकारात्मक हो सकते हैं, और $T=0$. उदाहरण के लिए, सेट दिया गया है $\{-7,-3,-2,9000,5,8\}$, उत्तर हाँ है क्योंकि उपसमुच्चय $\{-3,-2,5\}$ योग शून्य है.
• वह वैरिएंट जिसमें सभी इनपुट सकारात्मक हैं, और लक्ष्य योग सभी इनपुट के योग का बिल्कुल आधा है, यानी, $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ . एसएसपी के इस विशेष मामले को विभाजन समस्या के रूप में जाना जाता है।

एसएसपी को एक अनुकूलन समस्या के रूप में भी माना जा सकता है: एक उपसमुच्चय ढूंढें जिसका योग अधिकतम टी है, और उसके अधीन, जितना संभव हो टी के करीब। यह एनपी-हार्ड है, लेकिन कई एल्गोरिदम हैं जो इसे उचित रूप से जल्दी से हल कर सकते हैं अभ्यास।

एसएसपी नैपसैक समस्या और एकाधिक उपसमुच्चय योग समस्या का एक विशेष मामला है।

कम्प्यूटेशनल कठोरता

SSP की रन-टाइम जटिलता दो मापदंडों पर निर्भर करती है:

• n - इनपुट पूर्णांकों की संख्या. यदि n एक छोटी निश्चित संख्या है, तो समाधान के लिए एक विस्तृत खोज व्यावहारिक है।
• L - समस्या की सटीकता, समस्या को बताने के लिए लगने वाले द्विआधारी स्थानीय मानों की संख्या के रूप में बताई गई है। यदि L एक छोटी निश्चित संख्या है, तो गतिशील प्रोग्रामिंग एल्गोरिदम हैं जो इसे सटीक रूप से हल कर सकते हैं।

जैसे-जैसे n और L दोनों बड़े होते जाते हैं, SSP NP-हार्ड होता है। सबसे प्रसिद्ध एल्गोरिदम की जटिलता दो मापदंडों n और L में से छोटे में घातीय समय है। समस्या एनपी-हार्ड है, तब भी जब सभी इनपुट पूर्णांक सकारात्मक होते हैं (और लक्ष्य-योग टी इनपुट का एक हिस्सा है)। इसे 3SAT से प्रत्यक्ष कमी द्वारा सिद्ध किया जा सकता है। इसे 3-आयामी मिलान (3DM) से कमी करके भी सिद्ध किया जा सकता है:

• हमें 3DM का एक उदाहरण दिया गया है, जहां शीर्ष सेट W, X, Y हैं। प्रत्येक सेट में n शीर्ष हैं। वहाँ m किनारे हैं, जहाँ प्रत्येक किनारे में W,₂(एम+1)), ताकि एल किनारों की संख्या का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की संख्या से बड़ा हो।
• हम m धनात्मक पूर्णांकों के साथ SSP का एक उदाहरण बनाते हैं। पूर्णांकों का वर्णन उनके द्विआधारी निरूपण द्वारा किया जाता है। प्रत्येक इनपुट पूर्णांक को 3nL बिट्स द्वारा दर्शाया जा सकता है, जिसे L बिट्स के 3n ज़ोन में विभाजित किया गया है। प्रत्येक क्षेत्र एक शीर्ष से मेल खाता है।
• 3DM उदाहरण में प्रत्येक किनारे (w,x,y) के लिए, SSP उदाहरण में एक पूर्णांक होता है, जिसमें बिल्कुल तीन बिट्स 1 होते हैं: शीर्ष w, x, और y के क्षेत्रों में सबसे कम महत्वपूर्ण बिट्स . उदाहरण के लिए, यदि n=10 और L=3, और W=(0,...,9), X=(10,...,19), Y=(20,...,29), तो किनारे (0, 10, 20) को संख्या (2) द्वारा दर्शाया गया है⁰+2³⁰+2⁶⁰).
• एसएसपी उदाहरण में लक्ष्य योग टी को प्रत्येक क्षेत्र के सबसे कम-महत्वपूर्ण बिट में 1 के साथ पूर्णांक पर सेट किया गया है, यानी (2)⁰+2¹+...+2^3एन-1).
• यदि 3DM उदाहरण में पूर्ण मिलान है, तो SSP उदाहरण में संबंधित पूर्णांकों का योग बिल्कुल T प्राप्त करता है।
• इसके विपरीत, यदि SSP उदाहरण में बिल्कुल T योग के साथ एक उपसमुच्चय है, तो, चूंकि क्षेत्र पर्याप्त रूप से बड़े हैं ताकि एक क्षेत्र से दूसरे क्षेत्र में कोई स्थानांतरण न हो, योग को 3DM उदाहरण में पूर्ण मिलान के अनुरूप होना चाहिए।

निम्नलिखित वेरिएंट को एनपी-हार्ड के रूप में भी जाना जाता है:

• इनपुट पूर्णांक धनात्मक और ऋणात्मक दोनों हो सकते हैं, और लक्ष्य-योग T = 0. इसे धनात्मक पूर्णांक वाले वैरिएंट से घटाकर सिद्ध किया जा सकता है। उस वैरिएंट को SubsetSumPositive से और वर्तमान वैरिएंट को SubsetSumZero से निरूपित करें। SubsetSumPositive के एक उदाहरण (S, T) को देखते हुए, −T मान के साथ एक तत्व जोड़कर SubsetSumZero का एक उदाहरण बनाएं। SubsetSumPositive उदाहरण के समाधान को देखते हुए, −T जोड़ने से SubsetSumZero उदाहरण का समाधान प्राप्त होता है। इसके विपरीत, SubsetSumZero उदाहरण के समाधान को देखते हुए, इसमें −T होना चाहिए (चूंकि S में सभी पूर्णांक सकारात्मक हैं), इसलिए शून्य का योग प्राप्त करने के लिए, इसमें +T के योग के साथ S का एक उपसमुच्चय भी होना चाहिए, जो SubsetSumPositive उदाहरण का एक समाधान है।
• इनपुट पूर्णांक सकारात्मक हैं, और टी = योग(एस)/2। इसे सामान्य प्रकार से कमी करके भी सिद्ध किया जा सकता है; विभाजन समस्या देखें.

अनुरूप गणना समस्या #एसएसपी, जो लक्ष्य के योग के लिए उपसमुच्चय की संख्या की गणना करने के लिए कहती है, शार्प पी पूर्ण|#पी-पूर्ण है।

घातीय समय एल्गोरिदम

एन में समय घातांक में एसएसपी को हल करने के कई तरीके हैं।

समावेश-बहिष्करण

सबसे सरल समाधान|भोला एल्गोरिदम एन संख्याओं के सभी उपसमूहों के माध्यम से चक्र करना होगा और, उनमें से प्रत्येक के लिए, यह जांचना होगा कि उपसमुच्चय का योग सही संख्या में है या नहीं। चलने का समय व्यवस्थित है $O(2^{n}\cdot n)$, क्योंकि वहां हैं $2^{n}$ उपसमुच्चय और, प्रत्येक उपसमुच्चय की जाँच करने के लिए, हमें अधिकतम n तत्वों का योग करना होगा।

एल्गोरिथ्म को बाइनरी ट्री की गहराई-पहली खोज द्वारा कार्यान्वित किया जा सकता है: ट्री में प्रत्येक स्तर एक इनपुट संख्या से मेल खाता है; बायीं शाखा सेट से संख्या को बाहर करने से मेल खाती है, और दाहिनी शाखा संख्या को शामिल करने से मेल खाती है (इसलिए नाम समावेशन-बहिष्करण)। आवश्यक स्मृति है $O(n)$. रन-टाइम को कई अनुमानों द्वारा बेहतर बनाया जा सकता है:

• इनपुट संख्याओं को घटते क्रम में संसाधित करें।
• यदि किसी दिए गए नोड में शामिल पूर्णांक अब तक पाए गए सर्वोत्तम उपसमुच्चय के योग से अधिक है, तो नोड को काट दिया जाता है।
• यदि किसी दिए गए नोड में शामिल पूर्णांक, साथ ही शेष सभी पूर्णांक, अब तक पाए गए सर्वोत्तम उपसमुच्चय के योग से कम हैं, तो नोड को काट दिया जाता है।

होरोविट्ज़ और साहनी

1974 में, होरोविट्ज़ और सरताज साहनी एक तेज़ घातीय-समय एल्गोरिदम प्रकाशित किया, जो समय में चलता है $O(2^{n/2}\cdot (n/2))$, लेकिन बहुत अधिक स्थान की आवश्यकता है - $O(2^{n/2})$. एल्गोरिथ्म मनमाने ढंग से n तत्वों को दो सेटों में विभाजित करता है $n/2$ प्रत्येक। इन दो सेटों में से प्रत्येक के लिए, यह सभी के योगों की एक सूची संग्रहीत करता है $2^{n/2}$ इसके तत्वों के संभावित उपसमुच्चय। फिर इन दोनों सूचियों में से प्रत्येक को क्रमबद्ध किया जाता है। यहां तक ​​कि सबसे तेज़ तुलना सॉर्टिंग एल्गोरिदम का उपयोग करते हुए, इस चरण के लिए मर्जसॉर्ट को समय लगेगा $O(2^{n/2}n)$. हालाँकि, इसके लिए रकम की एक क्रमबद्ध सूची दी गई है $k$ तत्वों, सूची को (की शुरूआत के साथ दो क्रमबद्ध सूचियों तक विस्तारित किया जा सकता है$k+1$)वां तत्व, और इन दो क्रमबद्ध सूचियों को समय में मर्ज किया जा सकता है $O(2^{k})$. इस प्रकार, प्रत्येक सूची को समय पर क्रमबद्ध रूप में तैयार किया जा सकता है $O(2^{n/2})$. दो क्रमबद्ध सूचियों को देखते हुए, एल्गोरिदम जांच कर सकता है कि पहले सरणी का एक तत्व और दूसरे सरणी का एक तत्व समय में टी तक है या नहीं $O(2^{n/2})$. ऐसा करने के लिए, एल्गोरिदम पहले एरे से घटते क्रम में (सबसे बड़े तत्व से शुरू) और दूसरे एरे से बढ़ते क्रम में (सबसे छोटे तत्व से शुरू) गुजरता है। जब भी पहले एरे में वर्तमान तत्व और दूसरे एरे में वर्तमान तत्व का योग टी से अधिक होता है, तो एल्गोरिदम पहले एरे में अगले तत्व पर चला जाता है। यदि यह टी से कम है, तो एल्गोरिदम दूसरे सरणी में अगले तत्व पर चला जाता है। यदि T के योग वाले दो तत्व पाए जाते हैं, तो यह रुक जाता है। (दो तत्वों के योग की उप-समस्या को दो-योग के रूप में जाना जाता है।)

श्रोएप्पेल और शमीर

1981 में, रिचर्ड श्रोएप्पेल और आदि शमीर ने एक एल्गोरिदम प्रस्तुत किया होरोविट्ज़ और सानही पर आधारित, जिसके लिए समान रनटाइम की आवश्यकता होती है - $O(2^{n/2}\cdot (n/4))$, बहुत कम जगह - $O(2^{n/4})$. n/2 तत्वों के सभी उपसमूहों को पहले से बनाने और संग्रहीत करने के बजाय, वे तत्वों को n/4 तत्वों के 4 सेटों में विभाजित करते हैं, और न्यूनतम ढेर का उपयोग करके गतिशील रूप से n/2 तत्व जोड़े के सबसेट उत्पन्न करते हैं, जो उपरोक्त समय प्राप्त करता है और अंतरिक्ष की जटिलताएँ क्योंकि यह किया जा सकता है $O(k^{2}\log(k))$ और स्थान $O(k)$ लंबाई k की 4 सूचियाँ दी गई हैं।

स्थान आवश्यकताओं के कारण, एचएस एल्गोरिदम लगभग 50 पूर्णांकों तक के लिए व्यावहारिक है, और एसएस एल्गोरिदम 100 पूर्णांकों तक के लिए व्यावहारिक है।

हाउग्रेव-ग्राहम और जौक्स

2010 में, हाउग्रेव-ग्राहम और जौक्स एक संभाव्य एल्गोरिथ्म प्रस्तुत किया जो पिछले सभी एल्गोरिदम की तुलना में समय में तेजी से चलता है $O(2^{.337n})$ स्थान का उपयोग करना $O(2^{.256n})$. यह केवल निर्णय की समस्या को हल करता है, यह साबित नहीं कर सकता कि किसी दिए गए योग का कोई समाधान नहीं है, और टी के निकटतम सबसेट योग को वापस नहीं करता है।

हाउग्रेव-ग्राहम और जौक्स की तकनीकों को बाद में विस्तारित किया गया समय-जटिलता को लाना $O(2^{.291n})$.

छद्म-बहुपद समय गतिशील प्रोग्रामिंग समाधान

गतिशील प्रोग्रामिंग का उपयोग करके एसएसपी को छद्म-बहुपद समय में हल किया जा सकता है। मान लीजिए कि हमारे पास एक उदाहरण में तत्वों का निम्नलिखित क्रम है:

$x_{1},\ldots ,x_{N}$

हम एक अवस्था को पूर्णांकों के युग्म (i, s) के रूप में परिभाषित करते हैं। यह राज्य इस बात का प्रतिनिधित्व करता है कि

का एक अरिक्त उपसमुच्चय है $x_{1},\ldots ,x_{i}$ जो बताता है s.

प्रत्येक राज्य (i, s) के दो अगले राज्य हैं:

• (i+1, s), जिसका अर्थ है $x_{i+1}$ उपसमूह में शामिल नहीं है;
• (आई+1, एस+$x_{i+1}$), जिसका अर्थ है $x_{i+1}$ उपसमुच्चय में सम्मिलित है।

प्रारंभिक स्थिति (0, 0) से शुरू करके, स्थिति (एन, टी) की खोज के लिए किसी भी ग्राफ़ खोज एल्गोरिदम (उदाहरण के लिए चौड़ाई-पहली खोज) का उपयोग करना संभव है। यदि स्थिति पाई जाती है, तो पीछे जाकर हम बिल्कुल टी के योग के साथ एक उपसमुच्चय पा सकते हैं।

इस एल्गोरिदम का रन-टाइम राज्यों की संख्या में अधिकतम रैखिक है। राज्यों की संख्या विभिन्न संभावित योगों की संख्या से अधिकतम N गुना है। होने देना A ऋणात्मक मानों का योग हो और B सकारात्मक मानों का योग; विभिन्न संभावित योगों की संख्या अधिकतम B-A है, इसलिए कुल रनटाइम है $O(N(B-A))$. उदाहरण के लिए, यदि सभी इनपुट मान सकारात्मक हैं और कुछ स्थिरांक C से बंधे हैं, तो B अधिकतम N C है, इसलिए आवश्यक समय है $O(N^{2}C)$.

यह समाधान जटिलता सिद्धांत में बहुपद समय के रूप में नहीं गिना जाता है क्योंकि $B-A$ समस्या के आकार में बहुपद नहीं है, जो कि इसे दर्शाने के लिए उपयोग की जाने वाली बिट्स की संख्या है। यह एल्गोरिथम के मानों में बहुपद है A और B, जो बिट्स की संख्या में घातीय हैं। हालाँकि, यूनरी में एन्कोड किया गया सबसेट योग P में है, तब से एन्कोडिंग का आकार B-A में रैखिक है। इसलिए, सबसेट योग केवल कमजोर एनपी-पूर्ण है।

इस मामले के लिए कि प्रत्येक $x_{i}$ सकारात्मक है और एक निश्चित स्थिरांक से घिरा है C, 1999 में, पिसिंगर ने समय जटिलता वाला एक रैखिक समय एल्गोरिदम पाया $O(NC)$ (ध्यान दें कि यह समस्या के उस संस्करण के लिए है जहां लक्ष्य योग आवश्यक रूप से शून्य नहीं है, अन्यथा समस्या तुच्छ होगी)। 2015 में, कोइलियारिस और जू ने एक नियतिवादी पाया ${\tilde {O}}(T{\sqrt {N}})$ सबसेट योग समस्या के लिए एल्गोरिदम जहां T वह योग है जिसे हमें खोजने की आवश्यकता है। 2017 में, ब्रिंगमैन ने एक यादृच्छिक पाया ${\tilde {O}}(T+N)$ समय एल्गोरिथ्म. 2014 में, कर्टिस और सांचेस ने SIMD मशीनों में अत्यधिक स्केलेबल एक सरल रिकर्सन पाया $O(N(m-x_{\min })/p)$ समय और $O(N+m-x_{\min })$ स्थान, कहाँ p प्रसंस्करण तत्वों की संख्या है, $m=\min(s,\sum x_{i}-s)$ और $x_{\min }$ निम्नतम पूर्णांक है. यह अब तक ज्ञात सर्वोत्तम सैद्धांतिक समानांतर जटिलता है।

व्यावहारिक परिणामों की तुलना और एसएसपी के कठिन उदाहरणों के समाधान पर कर्टिस और सांचेस द्वारा चर्चा की गई है।

बहुपद समय सन्निकटन एल्गोरिदम

मान लीजिए कि सभी इनपुट सकारात्मक हैं। एसएसपी के लिए एक सन्निकटन एल्गोरिदम का लक्ष्य अधिकतम टी के योग और इष्टतम योग के कम से कम आर गुना के साथ एस का एक उपसमूह ढूंढना है, जहां आर (0,1) में एक संख्या है जिसे सन्निकटन अनुपात कहा जाता है।

सरल 1/2-अनुमान

निम्नलिखित अत्यंत सरल एल्गोरिदम का अनुमानित अनुपात 1/2 है:

• इनपुट को घटते मूल्य के आधार पर क्रमबद्ध करें;
• अगले सबसे बड़े इनपुट को सबसेट में रखें, जब तक वह वहां फिट बैठता है।

जब यह एल्गोरिदम समाप्त हो जाता है, तो या तो सभी इनपुट सबसेट में होते हैं (जो स्पष्ट रूप से इष्टतम है), या एक इनपुट है जो फिट नहीं होता है। ऐसा पहला इनपुट पिछले सभी इनपुट से छोटा है जो उपसमुच्चय में हैं और उपसमुच्चय में इनपुट का योग T/2 से अधिक है अन्यथा इनपुट भी T/2 से कम है और यह सेट में फिट होगा। T/2 से अधिक ऐसी राशि स्पष्ट रूप से OPT/2 से अधिक है।

पूर्ण-बहुपद समय सन्निकटन योजना

निम्नलिखित एल्गोरिदम प्रत्येक के लिए प्राप्त करता है $\epsilon >0$, का एक अनुमानित अनुपात $(1-\epsilon )$. इसका रन टाइम बहुपद है n और $1/\epsilon$. याद रखें कि n इनपुट की संख्या है और T उपसमुच्चय योग की ऊपरी सीमा है।

एक तत्व 0 को शामिल करने के लिए सूची L को प्रारंभ करें।

'प्रत्येक के लिए' मैं 1 से n तक 'करता हूँ'
    चलो यूiएक सूची बनें जिसमें L में सभी तत्व y और सभी योग x होंiएल में सभी y के लिए + y।
    यू क्रमित करेंiबढ़ते क्रम में
    L को खाली करें
    माना कि y, U का सबसे छोटा तत्व हैiL में y जोड़ें
    यू के 'प्रत्येक' तत्व z के लिएiबढ़ते क्रम में 'करो'
        // एक दूसरे के करीब संख्याओं को हटाकर सूची को ट्रिम करें
        // और लक्ष्य योग T से अधिक तत्वों को बाहर फेंक दें।
        'यदि' y + ε T/n < z ≤ T 'तब'
            y = z
            L में z जोड़ें

एल में सबसे बड़ा तत्व 'रिटर्न' करें।

ध्यान दें कि ट्रिमिंग चरण (प्रत्येक लूप के लिए आंतरिक) के बिना, सूची एल में सभी का योग शामिल होगा $2^{n}$ इनपुट के सबसेट. ट्रिमिंग चरण दो काम करता है:

• यह सुनिश्चित करता है कि L में शेष सभी राशियाँ T से नीचे हैं, इसलिए वे उप-योग समस्या का व्यवहार्य समाधान हैं।
• यह सुनिश्चित करता है कि सूची एल विरल है, यानी, प्रत्येक दो लगातार आंशिक-योगों के बीच का अंतर कम से कम है $\epsilon T/n$.

ये गुण मिलकर सूची की गारंटी देते हैं L से अधिक नहीं है $n/\epsilon$ तत्व; इसलिए रन-टाइम बहुपद है $n/\epsilon$.

जब एल्गोरिदम समाप्त होता है, यदि इष्टतम योग होता है L, फिर इसे वापस कर दिया जाता है और हमारा काम हो जाता है। अन्यथा, इसे पिछले ट्रिमिंग चरण में हटा दिया गया होगा। प्रत्येक ट्रिमिंग चरण अधिकतम एक योगात्मक त्रुटि प्रस्तुत करता है $\epsilon T/n$, इसलिए n चरण एक साथ अधिकतम की त्रुटि प्रस्तुत करते हैं $\epsilon T$. इसलिए, लौटाया गया समाधान कम से कम है ${\text{OPT}}-\epsilon T$ जो कम से कम है $(1-\epsilon ){\text{OPT}}$ .

उपरोक्त एल्गोरिदम उस स्थिति में एसएसपी का सटीक समाधान प्रदान करता है जब इनपुट संख्या छोटी (और गैर-नकारात्मक) होती है। यदि संख्याओं का कोई योग अधिक से अधिक निर्दिष्ट किया जा सकता है P बिट्स, फिर समस्या को लगभग हल करना $\epsilon =2^{-P}$ इसे बिल्कुल हल करने के बराबर है। फिर, अनुमानित उपसमुच्चय के लिए बहुपद समय एल्गोरिथ्म रनिंग टाइम बहुपद के साथ एक सटीक एल्गोरिदम बन जाता है n और $2^{P}$ (अर्थात, घातीय में P).

केलरर, मैनसिनी, पफ़रस्की और स्पेरान्ज़ा और केलरर, पफ़रस्की और पिसिंगर उपसमुच्चय राशि के लिए अन्य FPTAS-s प्रस्तुत करें।

यह भी देखें

• नैपसेक समस्या - एसएसपी का एक सामान्यीकरण जिसमें प्रत्येक इनपुट आइटम का एक मूल्य और एक वजन दोनों होता है। लक्ष्य मूल्य को अधिकतम करना है ताकि कुल वजन सीमित हो जाए।
• एकाधिक उपसमुच्चय योग समस्या - एसएसपी का एक सामान्यीकरण जिसमें व्यक्ति को कई उपसमुच्चय चुनने चाहिए।
• 3योग
• मर्कल-हेलमैन नैपसेक क्रिप्टोसिस्टम

अग्रिम पठन

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "35.5: The subset-sum problem". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.2: SP13, pg.223.
• Lagarias, J. C.; Odlyzko, A. M. (1985-01-01). "Solving low-density subset sum problems". Journal of the ACM. 32 (1): 229–246. doi:10.1145/2455.2461. ISSN 0004-5411. S2CID 885632.
• Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.