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

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

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

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

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

बढ़ते क्रम में सूची (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)$ होगी।

समानता

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

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

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

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

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

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

कार्यान्वयन के मुद्दे

रिकर्सन

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

स्पष्ट ढेर

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

ढेर का आकार

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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