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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

सबसे सरल समाधान एल्गोरिदम n संख्याओं के सभी उपसमूहों के माध्यम से चक्र करना होगा और, उनमें से प्रत्येक के लिए, यह जांचना होगा कि उपसमुच्चय का योग सही संख्या में है या नहीं है। चलने का समय $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})$ रूप में तैयार किया जा सकता है . दो क्रमबद्ध सूचियों को देखते हुए, एल्गोरिदम जांच कर सकता है कि पहले सरणी का तत्व और दूसरे सरणी का तत्व समय में T तक है या $O(2^{n/2})$ नहीं है . ऐसा करने के लिए, एल्गोरिदम पहले एरे से घटते क्रम में (सबसे बड़े तत्व से प्रारंभ) और दूसरे एरे से बढ़ते क्रम में (सबसे छोटे तत्व से प्रारंभ) निकलता है। जब भी पहले एरे में वर्तमान तत्व और दूसरे एरे में वर्तमान तत्व का योग T से अधिक होता है, तो एल्गोरिदम पहले एरे में अगले तत्व पर चला जाता है। यदि यह T से कम है, तो एल्गोरिदम दूसरे सरणी में अगले तत्व पर चला जाता है। यदि 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})$. यह केवल निर्णय की समस्या को हल करता है, यह सिद्ध नहीं कर सकता कि किसी दिए गए योग का कोई समाधान नहीं है, और T के निकटतम उपसमुच्चय योग को वापस नहीं करता है।

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

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

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

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

हम अवस्था को पूर्णांकों के युग्म (i, s) के रूप में परिभाषित करते हैं। यह स्तर इस बात का प्रतिनिधित्व करता है कि अरिक्त उपसमुच्चय $x_{1},\ldots ,x_{i}$ है जो s बताता है .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

initialize a list L to contain one element 0.

for each i from 1 to n do
    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
    sort Ui in ascending order
    make L empty 
    let y be the smallest element of Ui
    add y to L
    for each element z of Ui in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

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

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

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

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

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

केलरर, मैनसिनी, पफ़रस्की और स्पेरान्ज़ा और केलरर, पफ़रस्की और पिसिंगर उपसमुच्चय राशि के लिए अन्य एफपीटीएएस-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.