Partition problem
संख्या सिद्धांत और कंप्यूटर विज्ञान में, विभाजन समस्या, या संख्या विभाजन, यह तय करने का कार्य है कि क्या सकारात्मक पूर्णांकों के दिए गए बहुसमुच्चय S को दो उपसमुच्चय S1 और S2 में विभाजित किया जा सकता है ताकि S1 में संख्याओं का योग S2 में संख्याओं के योग के बराबर हो। हालाँकि विभाजन समस्या एन. पी.-पूर्ण है, एक छद्म-बहुपद समय गतिशील प्रोग्रामिंग समाधान है, और ऐसे शोध हैं जो कई उदाहरणों में समस्या को हल करते हैं, या तो इष्टतम रूप से या लगभग। इस कारण से, इसे "सबसे आसान कठिन समस्या" कहा गया है। विभाजन समस्या का एक अनुकूलन संस्करण है, जो मल्टीसेट एस को दो सबसेट एस1, एस2 में विभाजित करना है ताकि एस1 में तत्वों के योग और एस2 में तत्वों के योग के बीच का अंतर कम हो। अनुकूलन संस्करण एन. पी.-कठोर है, लेकिन व्यवहार में कुशलता से हल किया जा सकता है। विभाजन समस्या दो संबंधित समस्याओं का एक विशेष मामला हैः सबसेट सम समस्या में, लक्ष्य S का एक सबसेट खोजना है जिसका योग एक निश्चित लक्ष्य संख्या T है जिसे इनपुट के रूप में दिया जाता है (विभाजन समस्या वह विशेष मामला है जिसमें T, S का आधा योग है)। बहुपथ संख्या विभाजन में, एक पूर्णांक पैरामीटर k होता है, और लक्ष्य यह तय करना है कि क्या S को समान राशि के k उपसमुच्चय में विभाजित किया जा सकता है (विभाजन समस्या विशेष मामला है जिसमें k = 2)। हालाँकि, यह 3-विभाजन समस्या से काफी अलग हैः उस समस्या में, सबसेट की संख्या पहले से तय नहीं है-यह |S।// 3 होनी चाहिए, जहाँ प्रत्येक सबसेट में बिल्कुल 3 तत्व होने चाहिए। 3-विभाजन विभाजन की तुलना में बहुत कठिन है-इसमें कोई छद्म-बहुपद समय एल्गोरिथ्म नहीं है जब तक कि पी = एनपी न हो। S = {3,1,1,2,2,1} दिए गए उदाहरणों में विभाजन समस्या का एक वैध समाधान दो समुच्चय S1 = {1,1,1,2} और S2 = {{2,3} हैं। दोनों सेटों का योग 5 है, और वे विभाजन एस. ध्यान दें कि यह समाधान अद्वितीय नहीं है। S1 = {3,1,1} और S2 = {2,2,1} एक और समाधान है। सकारात्मक पूर्णांकों के प्रत्येक बहुसमुच्चय का समान योग के साथ दो उपसमुच्चय में विभाजन नहीं होता है। इस तरह के समुच्चय का एक उदाहरण S = {2,5} है। कम्प्यूटेशनल कठोरता विभाजन समस्या एन. पी. कठिन है। इसे सबसेट सम प्रॉब्लम से घटाकर साबित किया जा सकता है। सबसेटसम के एक उदाहरण में सकारात्मक पूर्णांकों का एक सेट S और एक लक्ष्य योग T होता है; लक्ष्य यह तय करना है कि क्या S का कोई सबसेट है जिसका योग बिल्कुल T है। इस तरह के एक उदाहरण को देखते हुए, विभाजन का एक उदाहरण बनाएँ जिसमें इनपुट सेट में मूल सेट के साथ दो तत्व होते हैंः z1 और z2, जिसमें z1 = योग (S) और z2 = 2T होता है। इस इनपुट सेट का योग योग (S) + z1 + z2 = 2 योग (S) + 2T है, इसलिए विभाजन के लिए लक्ष्य योग योग (S) + T है। मान लीजिए कि सबसेटसम उदाहरण के लिए एक समाधान S′ मौजूद है। फिर योग (S′) = T, इसलिए योग (S′z _ 1) = योग (S) + T, इसलिए S′z _ 1 विभाजन उदाहरण का समाधान है। इसके विपरीत, मान लीजिए कि विभाजन के उदाहरण का एक समाधान S "मौजूद है। फिर, S′ में या तो z1 या z2 होना चाहिए, लेकिन दोनों नहीं, क्योंकि उनका योग योग (S) + T से अधिक है। यदि S "में z1 है, तो इसमें S के तत्व ठीक T के योग के साथ होने चाहिए, इसलिए S" माइनस z1 सबसेटसम उदाहरण का एक समाधान है। यदि S "में z2 है, तो इसमें S के तत्व ठीक योग (S)-T के योग के साथ होने चाहिए, इसलिए S में अन्य वस्तुएं सबसेटसम उदाहरण का समाधान हैं। जैसा कि ऊपर उल्लेख किया गया है, विभाजन समस्या बहु-मार्ग-विभाजन और सबसेट-सम का एक विशेष मामला है। इसलिए, इन समस्याओं में से प्रत्येक के लिए विकसित एल्गोरिदम द्वारा इसे हल किया जा सकता है। बहु-मार्ग संख्या विभाजन के लिए विकसित एल्गोरिदम में शामिल हैंः लालची संख्या विभाजन-संख्याओं पर लूप, और प्रत्येक संख्या को सेट में रखता है जिसका वर्तमान योग सबसे छोटा है। यदि संख्याओं को क्रमबद्ध नहीं किया जाता है, तो रनटाइम ओ (एन) है और सन्निकटन अनुपात अधिकतम 3/2 है ("सन्निकटन अनुपात" का अर्थ है एल्गोरिथ्म आउटपुट में बड़ा योग, एक इष्टतम विभाजन में बड़े योग से विभाजित)। संख्याओं को क्रमबद्ध करने से रनटाइम बढ़कर ओ (एन लॉग एन) हो जाता है और सन्निकटन अनुपात 7/6 हो जाता है। यदि संख्याओं को समान रूप से [0,1] में वितरित किया जाता है, तो सन्निकटन अनुपात लगभग निश्चित रूप से और उम्मीद में है। सबसे बड़ी विभेदक विधि (जिसे करमरकर-कार्प एल्गोरिथ्म भी कहा जाता है) संख्याओं को अवरोही क्रम में क्रमबद्ध करती है और बार-बार उनके अंतरों द्वारा संख्याओं को प्रतिस्थापित करती है। रनटाइम जटिलता ओ (एन लॉग एन) है। सबसे खराब स्थिति में, इसका अनुमानित अनुपात समान है-अधिकतम 7/6। हालांकि, औसत मामले में यह लालची एल्गोरिथ्म की तुलना में बहुत बेहतर प्रदर्शन करता हैः जब संख्याओं को समान रूप से [0,1] में वितरित किया जाता है, तो इसका सन्निकटन अनुपात अधिक से अधिक उम्मीद में होता है। यह अनुकरण प्रयोगों में भी बेहतर प्रदर्शन करता है। मल्टीफिट एल्गोरिथ्म बिन पैकिंग के लिए एक एल्गोरिथ्म के साथ संयुक्त द्विआधारी खोज का उपयोग करता है। सबसे खराब स्थिति में, इसका अनुमानित अनुपात 8/7 है। सबसेट सम प्रॉब्लम में एक एफ. पी. टी. ए. एस. होता है जिसका उपयोग लक्ष्य राशि को योग (एस)/2 पर सेट करके विभाजन समस्या के लिए भी किया जा सकता है। सटीक एल्गोरिदम सटीक एल्गोरिदम हैं, जो हमेशा इष्टतम विभाजन पाते हैं। चूँकि समस्या एन. पी.-हार्ड है, इस तरह के एल्गोरिदम में सामान्य रूप से घातीय समय लग सकता है, लेकिन कुछ मामलों में व्यावहारिक रूप से उपयोग करने योग्य हो सकता है। बहुमार्ग संख्या विभाजन के लिए विकसित एल्गोरिदम में शामिल हैंः छद्म बहुपद समय संख्या विभाजन स्मृति लेता है, जहां इनपुट में सबसे बड़ी संख्या है। कम्प्लीट ग्रीडी एल्गोरिदम (सी. जी. ए.) एक द्विआधारी वृक्ष का निर्माण करके सभी विभाजनों पर विचार करता है। वृक्ष में प्रत्येक स्तर एक इनपुट संख्या से मेल खाता है, जहाँ मूल सबसे बड़ी संख्या से मेल खाता है, नीचे का स्तर अगली सबसे बड़ी संख्या से मेल खाता है, आदि। प्रत्येक शाखा एक अलग समूह से मेल खाती है जिसमें वर्तमान संख्या रखी जा सकती है। पेड़ को गहराई-प्रथम क्रम में पार करने के लिए केवल जगह की आवश्यकता होती है, लेकिन इसमें समय लग सकता है। एक लालची शोध का उपयोग करके रनटाइम में सुधार किया जा सकता हैः प्रत्येक स्तर में, पहले उस शाखा को विकसित करें जिसमें वर्तमान संख्या को सबसे छोटी राशि के साथ सेट में रखा जाता है। यह एल्गोरिथ्म पहले लालची संख्या विभाजन द्वारा पाया गया समाधान ढूंढता है, लेकिन फिर बेहतर समाधान खोजने के लिए आगे बढ़ता है। इस विचार के कुछ बदलाव उपसमुच्चय-राशि समस्या के लिए पूरी तरह से बहुपद-समय सन्निकटन योजनाएँ हैं, और इसलिए विभाजन समस्या के लिए भी। कम्पलीट करमरकर-कार्प एल्गोरिदम (सी. के. के.) एक द्विआधारी वृक्ष का निर्माण करके सभी विभाजनों पर विचार करता है। प्रत्येक स्तर संख्याओं की एक जोड़ी से मेल खाता है। बायीं शाखा उन्हें अलग-अलग उपसमुच्चय में रखने के अनुरूप है (यानी, उन्हें उनके अंतर से प्रतिस्थापित करना), और दाहिनी शाखा उन्हें एक ही उपसमुच्चय में रखने के अनुरूप है (यानी, उन्हें उनके योग से प्रतिस्थापित करना)। यह एल्गोरिथ्म पहले सबसे बड़ी विभेदक विधि द्वारा पाया गया समाधान ढूंढता है, लेकिन फिर बेहतर समाधान खोजने के लिए आगे बढ़ता है। यह यादृच्छिक उदाहरणों पर सी. जी. ए. की तुलना में काफी तेजी से चलता है। इसका लाभ तब बहुत अधिक होता है जब एक समान विभाजन मौजूद होता है, और परिमाण के कई क्रम के हो सकते हैं। व्यवहार में, मनमाने आकार की समस्याओं को सी. के. के. द्वारा हल किया जा सकता है यदि संख्याओं में अधिकतम 12 महत्वपूर्ण अंक हों। सी. के. के. कभी भी एक एल्गोरिथ्म के रूप में भी चल सकता हैः यह पहले के. के. समाधान ढूंढता है, और फिर समय के साथ उत्तरोत्तर बेहतर समाधान ढूंढता है (संभवतः सबसे खराब उदाहरणों के लिए, इष्टतमता तक पहुंचने के लिए घातीय समय की आवश्यकता होती है)। इसके लिए जगह की आवश्यकता होती है, लेकिन सबसे खराब स्थिति में समय लग सकता है। सबसेट सम के लिए विकसित एल्गोरिदम में शामिल हैंः होरोविट्ज़ और सांही-समय पर चलते हैं, लेकिन जगह की आवश्यकता होती है। श्रोपेल और शमीर-समय पर दौड़ते हैं और उन्हें बहुत कम जगह की आवश्यकता होती है। हाउग्रेव-ग्राहम और जौक्स-समय पर चलते हैं, लेकिन यह एक यादृच्छिक एल्गोरिथ्म है जो केवल निर्णय समस्या को हल करता है (अनुकूलन समस्या नहीं)। कठिन उदाहरण और चरण-संक्रमण सेट केवल एक के साथ, या कोई विभाजन नहीं होने पर उनके इनपुट आकार की तुलना में हल करना सबसे कठिन (या सबसे महंगा) होता है। जब सेट के आकार की तुलना में मान छोटे होते हैं, तो सही विभाजन की संभावना अधिक होती है। समस्या को "चरण संक्रमण" से गुजरने के लिए जाना जाता है; कुछ सेटों के लिए संभावित और दूसरों के लिए संभावना नहीं है। यदि m समुच्चय में किसी भी संख्या को व्यक्त करने के लिए आवश्यक बिट्स की संख्या है और n समुच्चय का आकार है तो कई समाधान होते हैं और कम या कोई समाधान नहीं होता है। जैसे-जैसे n और m बड़े होते जाते हैं, एक पूर्ण विभाजन की संभावना क्रमशः 1 या 0 हो जाती है। यह मूल रूप से जेंट और वाल्श द्वारा अनुभवजन्य साक्ष्य के आधार पर तर्क दिया गया था, फिर मर्टेंस द्वारा सांख्यिकीय भौतिकी के तरीकों का उपयोग किया गया था, और बाद में बोर्ग्स, चेज़ और पिटेल द्वारा साबित किया गया था। संभावित संस्करण एक संबंधित समस्या, कुछ हद तक जन्मदिन विरोधाभास के समान, इनपुट सेट के आकार को निर्धारित करने की है ताकि हमारे पास एक आधे की संभावना हो कि एक समाधान है, इस धारणा के तहत कि सेट में प्रत्येक तत्व यादृच्छिक रूप से 1 और कुछ दिए गए मूल्य के बीच समान वितरण के साथ चुना गया है। इस समस्या का समाधान जन्मदिन के विरोधाभास की तरह प्रति-सहज हो सकता है। प्रकार और सामान्यीकरण समान-कार्डिनलिटी विभाजन एक प्रकार है जिसमें दोनों भागों में समान राशि होने के अलावा समान संख्या में आइटम होने चाहिए। यह संस्करण एन. पी.-कठोर भी है। सबूत। कुछ n संख्याओं के साथ एक मानक विभाजन उदाहरण को देखते हुए, n शून्य जोड़कर एक समान-कार्डिनलिटी-विभाजन उदाहरण का निर्माण करें। स्पष्ट रूप से, नए उदाहरण में एक समान-कार्डिनलिटी समान-राशि विभाजन है यदि मूल उदाहरण में एक समान-राशि विभाजन है। संतुलित संख्या विभाजन भी देखें। विशिष्ट विभाजन एक प्रकार है जिसमें सभी इनपुट पूर्णांक भिन्न होते हैं। यह संस्करण एन. पी.-कठोर भी है। उत्पाद विभाजन पूर्णांकों के एक समूह को एक ही उत्पाद (एक ही राशि के बजाय) के साथ दो सेटों में विभाजित करने की समस्या है। यह समस्या प्रबल रूप से एन. पी.-कठोर है। कोवल्योव और पेस ने विभाजन-प्रकार की समस्याओं की एन. पी.-कठोरता को साबित करने के लिए एक सामान्य दृष्टिकोण पर चर्चा की। अनुप्रयोग विभाजन समस्या का एक अनुप्रयोग चुनावों के हेरफेर के लिए है। मान लीजिए कि तीन उम्मीदवार (ए, बी और सी) हैं। एक उम्मीदवार को अंक के आधार पर मतदान नियम का उपयोग करके चुना जाना चाहिए, उदाहरण के लिए। वीटो नियम (प्रत्येक मतदाता एक उम्मीदवार को वीटो करता है और सबसे कम वीटो वाला उम्मीदवार जीतता है)। यदि कोई गठबंधन यह सुनिश्चित करना चाहता है कि सी निर्वाचित हो, तो उन्हें अपने वोटों को ए और बी के बीच विभाजित करना चाहिए ताकि उनमें से प्रत्येक को मिलने वाले वीटो की सबसे कम संख्या को अधिकतम किया जा सके। यदि मतों को भारित किया जाता है, तो समस्या को विभाजन समस्या तक कम किया जा सकता है, और इस प्रकार इसे सी. के. के. का उपयोग करके कुशलता से हल किया जा सकता है। स्कोरिंग पर आधारित किसी भी अन्य मतदान नियम के लिए भी यही सच है। टिप्पणियाँ संदर्भ संख्या विभाजन कमजोर एन. पी.-पूर्ण समस्याएं