विभाजन और जीत कलनविधि (डिवाइड एंड कॉन्कर)

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

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

कुशल विभाजन और जीत कलनविधि अभिकल्पना करना कठिन हो सकता है। जैसा कि गणितीय आगमन में होता है, प्रायः समस्या को पुनरावर्ती समाधान करके उत्तरदायी बनाने के लिए सामान्यीकरण करना आवश्यक होता है। विभाजन और जीत कलनविधि की शुद्धता सामान्यतः गणितीय प्रेरण द्वारा सिद्ध होती है, और इसकी अभिकलनात्मक लागत प्रायः पुनरावृत्ति संबंधों को हल करके निर्धारित की जाती है।

फूट डालो और राज करो

बढ़ते क्रम में सूची (38, 27, 43, 3, 9, 82, 10) को क्रमबद्ध करने के लिए विभाजन और जीत दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: एक-तत्व सूची तुच्छ रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।

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

उदाहरण के लिए, n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n /2 संख्याओं मे प्रत्येक की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें, और दी गई सूची के क्रमबद्ध संस्करण को प्राप्त करने के लिए दोनों परिणामों को उचित रूप से अंतरापत्र करें ( चित्र देखें)। इस दृष्टिकोण को मर्ज सॉर्ट कलनविधि के रूप में जाना जाता है।

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

विभाजन और जीत का एक महत्वपूर्ण अनुप्रयोग अनुकूलीकरण में है, जहां यदि प्रत्येक चरण पर एक स्थिर कारक द्वारा खोज स्थान को कम ("छंटनी") किया जाता है, तो समग्र कलनविधि में प्रूनिंग चरण के समान विषम जटिलता होती है, साथ में प्रूनिंग कारक स्थिरांक पर निर्भर करता है (ज्यामितीय श्रृंखला को जोड़कर); इसे प्रून एंड सर्च के रूप में जाना जाता है।

प्रारंभिक ऐतिहासिक उदाहरण

इन कलनविधि के प्रारंभिक उदाहरण प्राथमिक रूप से ह्रास और जीत हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में खंडित किया जाता है, और वास्तव में इसे पुनरावृत्त रूप से समाधान किया जा सकता है।

बाइनरी खोज, एक कमी-और-जीत कलन विधि जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं, का एक लंबा इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथम का एक स्पष्ट विवरण 1946 में जॉन मौचली के एक लेख में दिखाई दिया, खोज की सुविधा के लिए वस्तुओं की एक क्रमबद्ध सूची का उपयोग करने का विचार कम से कम 200 ईसा पूर्व बेबिलोनिया तक था।एक अन्य प्राचीन कमी-और-जीत कलन विधि यूक्लिडियन कलन विधि है जो संख्याओं को छोटे और छोटे समतुल्य उपसमस्याओं में घटाकर दो संख्याओं के सबसे बड़े सामान्य विभाजक की गणना करता है, जो कई शताब्दियों ईसा पूर्व की है।

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

एक प्रारंभिक दो-उप-समस्या डी एंड सी कलन विधि जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था, मर्ज सॉर्ट कलन विधि है, जिसका आविष्कार जॉन वॉन न्यूमैन ने 1945 में किया था। एक अन्य उल्लेखनीय उदाहरण 1960 में अनातोली अलेक्सीविच करात्सुबा द्वारा आविष्कृत करात्सुबा एल्गोरिद्म है। अनातोली ए. करात्सुबा जो दो n-अंकीय संख्याओं का गुणा कर सकता है $O(n^{\log _{2}3})$ संचालन (बिग ओ नोटेशन में)। इस कलन विधि ने एंड्री कोलमोगोरोव के 1956 के अनुमान को खारिज कर दिया $\Omega (n^{2})$ उस कार्य के लिए संचालन की आवश्यकता होगी।

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

लाभ

कठिन समस्याओं का समाधान

विभाजन-और-जीत अवधारणात्मक रूप से कठिन समस्याओं को हल करने के लिए एक शक्तिशाली उपकरण है: इसके लिए केवल समस्या को उप-समस्याओं में खंडित करने, तुच्छ समस्याओं को हल करने और उप-समस्याओं को मूल समस्या से जोड़ने का एक तरीका है। इसी तरह, ह्रास-और-जीत केवल समस्या को एक छोटी समस्या में कम करने की आवश्यकता है, जैसे हनोई पहेली का क्लासिक टॉवर, जो $n$ ऊंचाई के टॉवर को स्थानांतरित कर $n-1$ ऊंचाई के टावर तक कम कर देता हैं।

एल्गोरिथम दक्षता

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

इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी लागत में सुधार किया। उदाहरण के लिए, यदि (ए) आधार समस्याओं का आकार स्थिर-परिबद्ध है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार $n$ के समानुपाती होता है और प्रत्येक (बी) चरण में,~ $n/p$ आकार की एक $p$ परिबद्ध संख्या संख्या की उप- समस्याएं हैं, तब विभाजन-और-जीत कलनविधि की लागत $O(n\log _{p}n)$ होगी।

समांतरवाद

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

मेमोरी एक्सेस

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

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

राउंडऑफ नियंत्रण

गोलाकार अंकगणित संगणना में, उदाहरण के लिए फ़्लोटिंग-पॉइंट संख्याओं के साथ, विभाजन-और-जीत कलनविधि सतही समकक्ष पुनरावृत्त विधि की तुलना में अधिक सटीक परिणाम दे सकता है। उदाहरण के लिए, N संख्याओं को या तो एक साधारण लूप द्वारा जोड़ा जा सकता है जो प्रत्येक डेटा को एक चर में जोड़ता है, या एक डी एंड सी कलनविधि द्वारा जिसे जोड़ीदार योग जो डेटा समुच्चय को दो हिस्सों में तोड़ता है, प्रत्येक आधे के योग की पुनरावर्ती गणना करता है, और पुनः दो योगफल को जोड़ता है। जबकि दूसरी विधि पहले की तरह समान संख्या में जोड़ करती है और पुनरावर्ती कॉल के उपरिव्यय का भुगतान करती है, यह सामान्यतः अधिक सटीक होती है।

कार्यान्वयन के लिए विवाद

रिकर्सन

विभाजन-और-जीत कलनविधि को स्वाभाविक रूप से पुनरावर्ती प्रक्रियाओं के रूप में परिपालित किया जाता है। उस स्थिति में, वर्तमान में हल की जा रही आंशिक उप-समस्याओं को प्रक्रिया कॉल स्टैक में स्वचालित रूप से संग्रहीत किया जाता है। एक पुनरावर्ती कार्य एक ऐसा कार्य है जो स्वयं को अपनी परिभाषा में आह्वान करता है।

स्पष्ट ढेर

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

स्टैक का आकार

डी एंड सी कलनविधि के पुनरावर्ती कार्यान्वयन में, यह सुनिश्चित करना चाहिए कि पुनरावर्तन स्टैक के लिए पर्याप्त मेमोरी आवंटित की गई है, अन्यथा स्टैक ओवरफ़्लो स्टैक ओवरफ्लो के कारण निष्पादन विफल हो सकता है। डी एंड सी कलनविधि जो समय-कुशल होते हैं, प्रायः अपेक्षाकृत कम पुनरावर्तन गहराई होती है। उदाहरण के लिए, क्विकसॉर्ट कलनविधि को परिपालित किया जा सकता है ताकि इसे कभी भी $n$ वस्तुओं को क्रमबद्ध करने के लिए अधिक $\log _{2}n$ नीड़ बद्ध  पुनरावर्ती कॉल की आवश्यकता न हो।

पुनरावर्ती प्रक्रियाओं का उपयोग करते समय स्टैक ओवरफ्लो को टालना कठिन हो सकता है क्योंकि कई संकलक मानते हैं कि रिकर्सन स्टैक मेमोरी का एक सन्निहित क्षेत्र है, और कुछ इसके लिए एक निश्चित मात्रा में स्थान आवंटित करते हैं। संकलक पुनरावर्ती स्टैक में अधिक जानकारी भी सहेज सकते हैं, जो दृढ़तः आवश्यक है, जैसे प्रतिगमन पता, अपरिवर्तनीय मापदण्ड और प्रक्रिया के आंतरिक चर। इस प्रकार, पुनरावर्ती प्रक्रिया के मापदण्ड और आंतरिक चर को कम करके या एक स्पष्ट स्टैक संरचना का उपयोग करके स्टैक ओवरफ़्लो के विपत्त‍ि को कम किया जा सकता है।

आधार मामलों का चयन

किसी भी पुनरावर्ती कलनविधि में, आधार समस्याओं की चयन में पर्याप्त स्वतंत्रता होती है, छोटी उप-समस्याएं जिन्हें पुनरावर्तन को समाप्त करने के लिए सीधे हल किया जाता है।

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

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

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

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

इस विचार के सामान्यीकृत संस्करण को पुनरावर्तन "अनरोलिंग" या "कोर्सनिंग" के रूप में जाना जाता है, और आधार समस्याओं को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव किया गया है।

इस विचार के सामान्यीकृत संस्करण को रिकर्सन अनोलिंग या मोटे होने के रूप में जाना जाता है, और आधार मामले को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव दिया गया है।

अतिव्यापी उप-समस्याओं के लिए गतिशील प्रोग्रामिंग

कुछ समस्याओं के लिए, शाखित पुनरावृत्ति एक ही उप-समस्या का कई बार मूल्यांकन कर सकती है। ऐसे समस्याओं में इन अतिव्यापी उपसमस्याओं के समाधानों को पहचानने और सुरक्षित रखने के योग्य हो सकता है, एक तकनीक जो सामान्यतः ज्ञापन के रूप में जाना जाता है। एक सीमा तक इसका पालन किया जाता है, यह डायनेमिक प्रोग्रामिंग जैसे बॉटम-अप विभाजन-और-जीत कलनविधि की ओर जाता है ।

यह भी देखें

• एकरा–बाजी विधि
• विघटित एकत्रीकरण क्रिया
• फोर्क-जॉइन मॉडल
• मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)
• गणितीय प्रेरण
• मानचित्र छोटा करना
• अन्वेषणात्मक (कंप्यूटर विज्ञान)