विभाजन-और-कन्कर एल्गोरिथ्म: Difference between revisions
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
[[कंप्यूटर विज्ञान]] में फूट डालो और जीतो [[एल्गोरिथ्म डिजाइन प्रतिमान]] है। डिवाइड-एंड-कॉनकोर एल्गोरिदम [[ रिकर्सन (कंप्यूटर विज्ञान) |रिकर्सन (कंप्यूटर विज्ञान)]] समस्या को ही या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तोड़ देता है | जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं। उप-समस्याओं के समाधान को तब मूल समस्या का समाधान देने के लिए संयोजित किया जाता है। | [[कंप्यूटर विज्ञान]] में फूट डालो और जीतो [[एल्गोरिथ्म डिजाइन प्रतिमान]] है। डिवाइड-एंड-कॉनकोर एल्गोरिदम [[ रिकर्सन (कंप्यूटर विज्ञान) |रिकर्सन (कंप्यूटर विज्ञान)]] समस्या को ही या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तोड़ देता है | जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं। उप-समस्याओं के समाधान को तब मूल समस्या का समाधान देने के लिए संयोजित किया जाता है। | ||
विभाजन और जीत विधि कई समस्याओं के लिए कुशल एल्गोरिदम का आधार है, जैसे [[छँटाई एल्गोरिथ्म]] (उदाहरण के लिए, त्वरित सॉर्ट | विभाजन और जीत विधि कई समस्याओं के लिए कुशल एल्गोरिदम का आधार है, जैसे [[छँटाई एल्गोरिथ्म]] (उदाहरण के लिए, त्वरित सॉर्ट [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]] ) गुणन एल्गोरिदम (उदाहरण के लिए [करत्सुबा [[ कलन विधि |कलन विधि]] ] अंक समस्या की निकटतम जोड़ी ढूंढना वाक्य रचनात्मक विश्लेषण (उदाहरण के लिए, [[टॉप-डाउन पार्सर]]) और असतत फूरियर ट्रांसफॉर्म [<nowiki/>[[असतत फूरियर रूपांतरण]]] की गणना करना।<ref>{{cite book |last1=Blahut |first1=Richard |title=सिग्नल प्रोसेसिंग के लिए फास्ट एल्गोरिदम|date=14 May 2014 |publisher=Cambridge University Press |isbn=978-0-511-77637-3 |pages=139–143}}</ref> | ||
कुशल फूट डालो और जीतो एल्गोरिदम डिजाइन करना कठिनाई हो सकता है। जैसा कि गणितीय आगमन में होता है | कुशल फूट डालो और जीतो एल्गोरिदम डिजाइन करना कठिनाई हो सकता है। जैसा कि गणितीय आगमन में होता है अधिकांशतः समस्या को पुनरावर्ती समाधान के लिए अनुकूल बनाने के लिए सामान्यीकरण करना आवश्यक होता है। विभाजन और जीत एल्गोरिथ्म की शुद्धता सामान्यतः [[गणितीय प्रेरण]] द्वारा सिद्ध होती है, और इसकी कम्प्यूटेशनल निवेश अधिकांशतः [[पुनरावृत्ति संबंध]] को हल करके निर्धारित की जाती है। | ||
== फूट डालो और राज करो == | == फूट डालो और राज करो == | ||
[[File:Merge sort algorithm diagram.svg|thumb|बढ़ते क्रम में सूची (38, 27, 43, 3, 9, 82, 10) को क्रमबद्ध करने के लिए फूट डालो और जीतो दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: -तत्व सूची तुच्छ रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।]]फूट डालो और जीतो प्रतिमान का उपयोग अधिकांशतः किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता है। इसका मूल विचार दी गई समस्या को दो या अधिक समान | [[File:Merge sort algorithm diagram.svg|thumb|बढ़ते क्रम में सूची (38, 27, 43, 3, 9, 82, 10) को क्रमबद्ध करने के लिए फूट डालो और जीतो दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: -तत्व सूची तुच्छ रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।]]फूट डालो और जीतो प्रतिमान का उपयोग अधिकांशतः किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता है। इसका मूल विचार दी गई समस्या को दो या अधिक समान किन्तु सरल उप-समस्याओं में विघटित करना है उन्हें बारी-बारी से हल करना और दी गई समस्या को हल करने के लिए उनके समाधानों की रचना करना है। पर्याप्त सरलता की समस्याएं सीधे हल हो जाती हैं। | ||
उदाहरण के लिए | उदाहरण के लिए n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n/2 संख्याओं की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें और दी गई सूची का क्रमबद्ध संस्करण प्राप्त करने के लिए दोनों परिणामों को उचित रूप से इंटरलीव करें (देखें) चित्र)। इस दृष्टिकोण को मर्ज सॉर्ट एल्गोरिथम के रूप में जाना जाता है। | ||
विभाजित करें और जीतें नाम को कभी-कभी एल्गोरिदम पर प्रयुक्त किया जाता है जो प्रत्येक समस्या को केवल उप-समस्या तक कम कर देता है, जैसे बाइनरी खोज एल्गोरिदम क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक एल्गोरिदम में इसका एनालॉग | विभाजित करें और जीतें नाम को कभी-कभी एल्गोरिदम पर प्रयुक्त किया जाता है जो प्रत्येक समस्या को केवल उप-समस्या तक कम कर देता है, जैसे बाइनरी खोज एल्गोरिदम क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक एल्गोरिदम में इसका एनालॉग रूट-खोज के लिए द्विभाजन एल्गोरिदम) कलन विधि)।<ref name="CormenLeiserson2009">{{cite book|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|author4=Clifford Stein|title=एल्गोरिदम का परिचय|url=https://books.google.com/books?id=aefUBQAAQBAJ&q=%22Divide-and-conquer%22|date=31 July 2009|publisher=MIT Press|isbn=978-0-262-53305-8}}</ref> इन एल्गोरिदम को सामान्य डिवाइड-एंड-कॉनकॉर एल्गोरिदम की तुलना में अधिक कुशलता से प्रयुक्त किया जा सकता है; विशेष रूप से, यदि वे [[पूंछ पुनरावर्तन]] का उपयोग करते हैं, तो उन्हें साधारण [[ पाश (कंप्यूटिंग) |पाश (कंप्यूटिंग)]] में परिवर्तित किया जा सकता है। चूंकि, इस व्यापक परिभाषा के अनुसार, प्रत्येक एल्गोरिदम जो रिकर्सन या लूप का उपयोग करता है, उसे विभाजन और जीत एल्गोरिदम के रूप में माना जा सकता है। इसलिए, कुछ लेखकों का मानना है कि फूट डालो और जीतो नाम का उपयोग तभी किया जाना चाहिए जब प्रत्येक समस्या दो या दो से अधिक उप-समस्याएं उत्पन्न कर सकती है।<ref>Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.</ref> एकल-उप-समस्या वर्ग के अतिरिक्त नाम घटाना और जीतना प्रस्तावित किया गया है।<ref>Anany V. Levitin, ''Introduction to the Design and Analysis of Algorithms'' (Addison Wesley, 2002).</ref> फूट डालो और जीतो का महत्वपूर्ण अनुप्रयोग अनुकूलन में है, जहां यदि प्रत्येक चरण में स्थिर कारक द्वारा खोज स्थान को कम (छंटनी) किया जाता है, तो समग्र एल्गोरिथ्म में प्रूनिंग चरण के समान विषम जटिलता होती है, जिसमें प्रूनिंग कारक (ज्यामितीय श्रृंखला को जोड़कर) पर निर्भर करता है; इसे [[छँटाई और खोज]] के रूप में जाना जाता है। | ||
फूट डालो और जीतो का महत्वपूर्ण अनुप्रयोग अनुकूलन में है, जहां यदि प्रत्येक चरण में स्थिर कारक द्वारा खोज स्थान को कम (छंटनी) किया जाता है, तो समग्र एल्गोरिथ्म में प्रूनिंग चरण के समान विषम जटिलता होती है, जिसमें प्रूनिंग कारक (ज्यामितीय श्रृंखला को जोड़कर) पर निर्भर करता है; इसे [[छँटाई और खोज]] के रूप में जाना जाता है। | |||
== प्रारंभिक ऐतिहासिक उदाहरण == | == प्रारंभिक ऐतिहासिक उदाहरण == | ||
इन एल्गोरिदम के प्रारंभिक उदाहरण मुख्य रूप से घटते हैं और जीतते हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में टूट जाती है, और वास्तव में इसे पुनरावृत्त रूप से हल किया जा सकता है। | इन एल्गोरिदम के प्रारंभिक उदाहरण मुख्य रूप से घटते हैं और जीतते हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में टूट जाती है, और वास्तव में इसे पुनरावृत्त रूप से हल किया जा सकता है। | ||
बाइनरी खोज, कमी-और-जीत एल्गोरिथ्म जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं | बाइनरी खोज, कमी-और-जीत एल्गोरिथ्म जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं का लंबा इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथ्म का स्पष्ट विवरण 1946 में [[जॉन मौचली]] के लेख में दिखाई दिया, खोज की सुविधा के लिए वस्तुओं की क्रमबद्ध सूची का उपयोग करने का विचार कम से कम 200 ईसा पूर्व [[ बेबिलोनिया |बेबिलोनिया]] तक था।<ref name=Knuth3/> अन्य प्राचीन कमी-और-जीत एल्गोरिथ्म [[यूक्लिडियन एल्गोरिथ्म]] है जो संख्याओं को छोटे और छोटे समतुल्य उपसमस्याओं में घटाकर दो संख्याओं के सबसे बड़े सामान्य विभाजक की गणना करता है, जो कई शताब्दियों ईसा पूर्व की है। | ||
कई उप-समस्याओं के साथ विभाजित और जीत एल्गोरिथ्म का प्रारंभिक उदाहरण [[कार्ल फ्रेडरिक गॉस]] का 1805 का विवरण है जिसे अब कूली-तुकी एफएफटी एल्गोरिदम कहा जाता है। कूली-तुकी फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम।<ref name=Heideman84>Heideman, M. T., D. H. Johnson, and C. S. Burrus, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Gauss and the history of the fast Fourier transform]", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</ref> चूंकि उन्होंने मात्रात्मक रूप से [[एल्गोरिदम का विश्लेषण]] नहीं किया, और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें सदी बाद फिर से खोजा नहीं गया। | कई उप-समस्याओं के साथ विभाजित और जीत एल्गोरिथ्म का प्रारंभिक उदाहरण [[कार्ल फ्रेडरिक गॉस]] का 1805 का विवरण है जिसे अब कूली-तुकी एफएफटी एल्गोरिदम कहा जाता है। कूली-तुकी फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम।<ref name=Heideman84>Heideman, M. T., D. H. Johnson, and C. S. Burrus, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Gauss and the history of the fast Fourier transform]", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</ref> चूंकि उन्होंने मात्रात्मक रूप से [[एल्गोरिदम का विश्लेषण]] नहीं किया, और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें सदी बाद फिर से खोजा नहीं गया। | ||
| Line 32: | Line 31: | ||
=== एल्गोरिथम दक्षता === | === एल्गोरिथम दक्षता === | ||
फूट डालो और जीतो प्रतिमान अधिकांशतः कुशल एल्गोरिदम की खोज में सहायता करता है। यह कुंजी थी, उदाहरण के लिए, करात्सुबा की तेजी से गुणन विधि, क्विकसॉर्ट और मर्जसॉर्ट एल्गोरिदम, आव्युह गुणन के लिए [[सड़क एल्गोरिथ्म]] | फूट डालो और जीतो प्रतिमान अधिकांशतः कुशल एल्गोरिदम की खोज में सहायता करता है। यह कुंजी थी, उदाहरण के लिए, करात्सुबा की तेजी से गुणन विधि, क्विकसॉर्ट और मर्जसॉर्ट एल्गोरिदम, आव्युह गुणन के लिए [[सड़क एल्गोरिथ्म]] और तेजी से फूरियर रूपांतरण। | ||
इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी जटिलता में सुधार किया। उदाहरण के लिए, यदि (ए) रिकर्सन (कंप्यूटर विज्ञान) का आकार स्थिर है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार के समानुपाती होता है <math>n</math>, और (बी) परिबद्ध संख्या है <math>p</math> आकार की उप-समस्याओं की ~ <math>n/p</math> प्रत्येक चरण में, तब फूट डालो और जीतो एल्गोरिथम की निवेश होगी <math>O(n\log_{p}n)</math>. | इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी जटिलता में सुधार किया। उदाहरण के लिए, यदि (ए) रिकर्सन (कंप्यूटर विज्ञान) का आकार स्थिर है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार के समानुपाती होता है <math>n</math>, और (बी) परिबद्ध संख्या है <math>p</math> आकार की उप-समस्याओं की ~ <math>n/p</math> प्रत्येक चरण में, तब फूट डालो और जीतो एल्गोरिथम की निवेश होगी <math>O(n\log_{p}n)</math>. | ||
Revision as of 13:11, 20 June 2023
कंप्यूटर विज्ञान में फूट डालो और जीतो एल्गोरिथ्म डिजाइन प्रतिमान है। डिवाइड-एंड-कॉनकोर एल्गोरिदम रिकर्सन (कंप्यूटर विज्ञान) समस्या को ही या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तोड़ देता है | जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं। उप-समस्याओं के समाधान को तब मूल समस्या का समाधान देने के लिए संयोजित किया जाता है।
विभाजन और जीत विधि कई समस्याओं के लिए कुशल एल्गोरिदम का आधार है, जैसे छँटाई एल्गोरिथ्म (उदाहरण के लिए, त्वरित सॉर्ट मर्ज़ सॉर्ट ) गुणन एल्गोरिदम (उदाहरण के लिए [करत्सुबा कलन विधि ] अंक समस्या की निकटतम जोड़ी ढूंढना वाक्य रचनात्मक विश्लेषण (उदाहरण के लिए, टॉप-डाउन पार्सर) और असतत फूरियर ट्रांसफॉर्म [असतत फूरियर रूपांतरण] की गणना करना।[1]
कुशल फूट डालो और जीतो एल्गोरिदम डिजाइन करना कठिनाई हो सकता है। जैसा कि गणितीय आगमन में होता है अधिकांशतः समस्या को पुनरावर्ती समाधान के लिए अनुकूल बनाने के लिए सामान्यीकरण करना आवश्यक होता है। विभाजन और जीत एल्गोरिथ्म की शुद्धता सामान्यतः गणितीय प्रेरण द्वारा सिद्ध होती है, और इसकी कम्प्यूटेशनल निवेश अधिकांशतः पुनरावृत्ति संबंध को हल करके निर्धारित की जाती है।
फूट डालो और राज करो
फूट डालो और जीतो प्रतिमान का उपयोग अधिकांशतः किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता है। इसका मूल विचार दी गई समस्या को दो या अधिक समान किन्तु सरल उप-समस्याओं में विघटित करना है उन्हें बारी-बारी से हल करना और दी गई समस्या को हल करने के लिए उनके समाधानों की रचना करना है। पर्याप्त सरलता की समस्याएं सीधे हल हो जाती हैं।
उदाहरण के लिए n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n/2 संख्याओं की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें और दी गई सूची का क्रमबद्ध संस्करण प्राप्त करने के लिए दोनों परिणामों को उचित रूप से इंटरलीव करें (देखें) चित्र)। इस दृष्टिकोण को मर्ज सॉर्ट एल्गोरिथम के रूप में जाना जाता है।
विभाजित करें और जीतें नाम को कभी-कभी एल्गोरिदम पर प्रयुक्त किया जाता है जो प्रत्येक समस्या को केवल उप-समस्या तक कम कर देता है, जैसे बाइनरी खोज एल्गोरिदम क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक एल्गोरिदम में इसका एनालॉग रूट-खोज के लिए द्विभाजन एल्गोरिदम) कलन विधि)।[2] इन एल्गोरिदम को सामान्य डिवाइड-एंड-कॉनकॉर एल्गोरिदम की तुलना में अधिक कुशलता से प्रयुक्त किया जा सकता है; विशेष रूप से, यदि वे पूंछ पुनरावर्तन का उपयोग करते हैं, तो उन्हें साधारण पाश (कंप्यूटिंग) में परिवर्तित किया जा सकता है। चूंकि, इस व्यापक परिभाषा के अनुसार, प्रत्येक एल्गोरिदम जो रिकर्सन या लूप का उपयोग करता है, उसे विभाजन और जीत एल्गोरिदम के रूप में माना जा सकता है। इसलिए, कुछ लेखकों का मानना है कि फूट डालो और जीतो नाम का उपयोग तभी किया जाना चाहिए जब प्रत्येक समस्या दो या दो से अधिक उप-समस्याएं उत्पन्न कर सकती है।[3] एकल-उप-समस्या वर्ग के अतिरिक्त नाम घटाना और जीतना प्रस्तावित किया गया है।[4] फूट डालो और जीतो का महत्वपूर्ण अनुप्रयोग अनुकूलन में है, जहां यदि प्रत्येक चरण में स्थिर कारक द्वारा खोज स्थान को कम (छंटनी) किया जाता है, तो समग्र एल्गोरिथ्म में प्रूनिंग चरण के समान विषम जटिलता होती है, जिसमें प्रूनिंग कारक (ज्यामितीय श्रृंखला को जोड़कर) पर निर्भर करता है; इसे छँटाई और खोज के रूप में जाना जाता है।
प्रारंभिक ऐतिहासिक उदाहरण
इन एल्गोरिदम के प्रारंभिक उदाहरण मुख्य रूप से घटते हैं और जीतते हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में टूट जाती है, और वास्तव में इसे पुनरावृत्त रूप से हल किया जा सकता है।
बाइनरी खोज, कमी-और-जीत एल्गोरिथ्म जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं का लंबा इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथ्म का स्पष्ट विवरण 1946 में जॉन मौचली के लेख में दिखाई दिया, खोज की सुविधा के लिए वस्तुओं की क्रमबद्ध सूची का उपयोग करने का विचार कम से कम 200 ईसा पूर्व बेबिलोनिया तक था।[5] अन्य प्राचीन कमी-और-जीत एल्गोरिथ्म यूक्लिडियन एल्गोरिथ्म है जो संख्याओं को छोटे और छोटे समतुल्य उपसमस्याओं में घटाकर दो संख्याओं के सबसे बड़े सामान्य विभाजक की गणना करता है, जो कई शताब्दियों ईसा पूर्व की है।
कई उप-समस्याओं के साथ विभाजित और जीत एल्गोरिथ्म का प्रारंभिक उदाहरण कार्ल फ्रेडरिक गॉस का 1805 का विवरण है जिसे अब कूली-तुकी एफएफटी एल्गोरिदम कहा जाता है। कूली-तुकी फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम।[6] चूंकि उन्होंने मात्रात्मक रूप से एल्गोरिदम का विश्लेषण नहीं किया, और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें सदी बाद फिर से खोजा नहीं गया।
प्रारंभिक दो-उप-समस्या डी एंड सी एल्गोरिथ्म जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था, मर्ज सॉर्ट एल्गोरिथ्म है, जिसका आविष्कार जॉन वॉन न्यूमैन ने 1945 में किया था।[7] अन्य उल्लेखनीय उदाहरण 1960 में अनातोली अलेक्सीविच करात्सुबा द्वारा आविष्कृत करात्सुबा एल्गोरिद्म है। अनातोली ए. करात्सुबा[8] जो दो n-अंकीय संख्याओं का गुणा कर सकता है संचालन (बिग ओ नोटेशन में)। इस एल्गोरिथ्म ने एंड्री कोलमोगोरोव के 1956 के अनुमान को खारिज कर दिया उस कार्य के लिए संचालन की आवश्यकता होगी।
फूट डालो और जीतो एल्गोरिद्म के अन्य उदाहरण के रूप में, जिसमें मूल रूप से कंप्यूटर सम्मिलित नहीं थे, डोनाल्ड नुथ उस विधि को देते हैं जो डाकघर सामान्यतः मेल को रूट करने के लिए उपयोग करता है: पत्रों को अलग-अलग भौगोलिक क्षेत्रों के लिए अलग-अलग बैग में सॉर्ट किया जाता है, इनमें से प्रत्येक बैग को स्वयं सॉर्ट किया जाता है। छोटे उप-क्षेत्रों के लिए बैचों में, और इसी तरह जब तक वे वितरित नहीं हो जाते।[5] यह आपको कामयाबी मिले से संबंधित है, जिसका वर्णन IBM 80 सीरीज़ कार्ड सॉर्टर्स | पंच-कार्ड सॉर्टिंग मशीनों के लिए 1929 की शुरुआत में किया गया था।[5]
लाभ
कठिन समस्याओं का समाधान
फूट डालो और जीतो अवधारणात्मक रूप से कठिन समस्याओं को हल करने के लिए शक्तिशाली उपकरण है: इसके लिए केवल समस्या को उप-समस्याओं में तोड़ने, तुच्छ स्थितियों को हल करने और उप-समस्याओं को मूल समस्या से जोड़ने का विधि है। इसी तरह, घटाना और जीतना केवल समस्या को छोटी समस्या में कम करने की आवश्यकता है, जैसे हनोई पहेली का क्लासिक टॉवर, जो ऊंचाई के टावर को कम कर देता है ऊंचाई के टॉवर को स्थानांतरित करने के लिए .
एल्गोरिथम दक्षता
फूट डालो और जीतो प्रतिमान अधिकांशतः कुशल एल्गोरिदम की खोज में सहायता करता है। यह कुंजी थी, उदाहरण के लिए, करात्सुबा की तेजी से गुणन विधि, क्विकसॉर्ट और मर्जसॉर्ट एल्गोरिदम, आव्युह गुणन के लिए सड़क एल्गोरिथ्म और तेजी से फूरियर रूपांतरण।
इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी जटिलता में सुधार किया। उदाहरण के लिए, यदि (ए) रिकर्सन (कंप्यूटर विज्ञान) का आकार स्थिर है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार के समानुपाती होता है , और (बी) परिबद्ध संख्या है आकार की उप-समस्याओं की ~ प्रत्येक चरण में, तब फूट डालो और जीतो एल्गोरिथम की निवेश होगी .
समानता
मल्टी-प्रोसेसर मशीनों, विशेष रूप से साझा-मेमोरी प्रणाली में निष्पादन के लिए विभाजित और जीत एल्गोरिदम स्वाभाविक रूप से अनुकूलित होते हैं, जहां प्रोसेसर के बीच डेटा के संचार को पहले से नियोजित करने की आवश्यकता नहीं होती है क्योंकि अलग-अलग प्रोसेसर पर अलग-अलग उप-समस्याओं को निष्पादित किया जा सकता है।
मेमोरी एक्सेस
फूट डालो और जीतो एल्गोरिदम स्वाभाविक रूप से मेमोरी कैश का कुशल उपयोग करते हैं। इसका कारण यह है कि बार उप-समस्या अधिक छोटी हो जाती है, इसे और इसकी सभी उप-समस्याओं को, सिद्धांत रूप में, धीमी मुख्य मेमोरी तक पहुंच के बिना कैश के अन्दर हल किया जा सकता है। इस तरह से कैश का दोहन करने के लिए डिज़ाइन किया गया एल्गोरिदम कैश-बेखबर एल्गोरिदम कहा जाता है। कैश-बेखबर, क्योंकि इसमें कैश आकार को स्पष्ट पैरामीटर के रूप में सम्मिलित नहीं किया गया है।[9] इसके अतिरिक्त, डी एंड सी एल्गोरिदम को महत्वपूर्ण एल्गोरिदम (जैसे, सॉर्टिंग, एफएफटी, और आव्युह गुणन) के लिए डिज़ाइन किया जा सकता है जिससे वे इष्टतम कैश-बेखबर एल्गोरिदम हो सकें - वे कैश आकार की परवाह किए बिना एसिम्प्टोटिक अर्थ में कैश का उपयोग संभवतः इष्टतम तरीके से करते हैं। इसके विपरीत, कैश का दोहन करने का पारंपरिक विधि ब्लॉकिंग है, जैसा कि पाश घोंसला अनुकूलन में होता है, जहाँ समस्या को स्पष्ट रूप से उपयुक्त आकार के टुकड़ों में विभाजित किया जाता है - यह कैश का भी उतम उपयोग कर सकता है, किन्तु केवल तभी जब एल्गोरिथ्म विशिष्ट के लिए ट्यून किया जाता है किसी विशेष मशीन का कैश आकार।
अन्य पदानुक्रमित भंडारण प्रणालियों के संबंध में समान लाभ उपस्थित है, जैसे कि गैर-समान मेमोरी एक्सेस या आभासी मेमोरी , साथ ही साथ कैश के कई स्तरों के लिए: बार उप-समस्या अधिक छोटी हो जाती है, इसे दिए गए स्तर के अन्दर हल किया जा सकता है पदानुक्रम, उच्च (धीमे) स्तरों तक पहुँच के बिना।
राउंडऑफ नियंत्रण
गोलाकार अंकगणितीय संगणनाओं में, उदा. तैरनेवाला स्थल नंबरों के साथ, डिवाइड-एंड-कॉनकॉर एल्गोरिथम सतही समकक्ष पुनरावृत्त विधि की तुलना में अधिक स्पष्ट परिणाम दे सकता है। उदाहरण के लिए, एन नंबरों को या तो साधारण लूप द्वारा जोड़ा जा सकता है जो प्रत्येक डेटा को चर में जोड़ता है, या डी एंड सी एल्गोरिथ्म द्वारा जोड़ीदार योग कहा जाता है जो डेटा समुच्चय को दो हिस्सों में तोड़ता है, प्रत्येक आधे के योग की पुनरावर्ती गणना करता है, और फिर जोड़ता है दो रकम। जबकि दूसरी विधि पहले की तरह समान संख्या में जोड़ करती है और पुनरावर्ती कॉल के ओवरहेड का भुगतान करती है, यह सामान्यतः अधिक स्पष्ट होती है।[10]
कार्यान्वयन के उदेश समुच्चय
रिकर्सन
फूट डालो और जीतो एल्गोरिदम को स्वाभाविक रूप से रिकर्सन (कंप्यूटर विज्ञान) के रूप में प्रयुक्त किया जाता है। उस स्थिति में, वर्तमान में हल की जा रही आंशिक उप-समस्याओं को स्वचालित रूप से कॉल स्टैक में संग्रहीत किया जाता है। पुनरावर्ती कार्य ऐसा कार्य है जो स्वयं को अपनी परिभाषा में बुलाता है।
स्पष्ट ढेर
विभाजन और जीत एल्गोरिदम को गैर-पुनरावर्ती प्रोग्राम द्वारा भी कार्यान्वित किया जा सकता है जो आंशिक उप-समस्याओं को कुछ स्पष्ट डेटा संरचना, जैसे स्टैक (डेटा संरचना), कतार (डेटा संरचना), या प्राथमिकता कतार में संग्रहीत करता है। यह दृष्टिकोण उप-समस्या के चुनाव में अधिक स्वतंत्रता की अनुमति देता है जिसे अगले हल किया जाना है, विशेषता जो कुछ अनुप्रयोगों में महत्वपूर्ण है - उदा। इन चौड़ाई पहली रिकर्सन |ब्रेड्थ-फर्स्ट रिकर्सन और फंक्शन ऑप्टिमाइज़ेशन के लिए शाखा और बंधन मेथड। यह दृष्टिकोण प्रोग्रामिंग भाषाओं में मानक समाधान भी है जो पुनरावर्ती प्रक्रियाओं के लिए समर्थन प्रदान नहीं करता है।
ढेर का आकार
डी एंड सी एल्गोरिदम के पुनरावर्ती कार्यान्वयन में, किसी को यह सुनिश्चित करना चाहिए कि रिकर्सन स्टैक के लिए पर्याप्त मेमोरी आवंटित की गई है, अन्यथा स्टैक ओवरफ़्लो के कारण निष्पादन विफल हो सकता है। डी एंड सी एल्गोरिदम जो समय-कुशल होते हैं, अधिकांशतः अपेक्षाकृत कम पुनरावर्तन गहराई होती है। उदाहरण के लिए, क्विकसॉर्ट एल्गोरिथम को प्रयुक्त किया जा सकता है जिससे इसे कभी भी अधिक की आवश्यकता न हो क्रमबद्ध करने के लिए नेस्टेड पुनरावर्ती कॉल सामान।
रिकर्सिव प्रक्रियाओं का उपयोग करते समय स्टैक ओवरफ्लो से बचना कठिनाई हो सकता है क्योंकि कई कंपाइलर मानते हैं कि रिकर्सन स्टैक मेमोरी का सन्निहित क्षेत्र है, और कुछ इसके लिए निश्चित मात्रा में स्थान आवंटित करते हैं। कंपाइलर पुनरावर्ती स्टैक में अधिक जानकारी भी सहेज सकते हैं, जो कड़ाई से आवश्यक है, जैसे रिटर्न एड्रेस, अपरिवर्तनीय पैरामीटर और प्रक्रिया के आंतरिक चर। इस प्रकार, रिकर्सिव प्रक्रिया के पैरामीटर और आंतरिक चर को कम करके या स्पष्ट स्टैक संरचना का उपयोग करके स्टैक ओवरफ़्लो का कठिन परिस्थिति कम किया जा सकता है।
आधार स्थितियों का चयन
किसी भी पुनरावर्ती एल्गोरिदम में, आधार स्थितियों की पसंद में अधिक स्वतंत्रता होती है, छोटी उप-समस्याएं जो पुनरावर्तन को समाप्त करने के लिए सीधे हल हो जाती हैं।
सबसे छोटे या सरलतम संभावित आधार स्थितियों को चुनना अधिक सुरुचिपूर्ण है और सामान्यतः सरल कार्यक्रमों की ओर जाता है, क्योंकि विचार करने के लिए कम मामले होते हैं और उन्हें हल करना आसान होता है। उदाहरण के लिए, FFT एल्गोरिथम रिकर्सन को रोक सकता है जब इनपुट नमूना होता है, और क्विकॉर्ट लिस्ट-सॉर्टिंग एल्गोरिथम तब रुक सकता है जब इनपुट खाली सूची हो; दोनों उदाहरणों में, विचार करने के लिए केवल आधार मामला है, और इसके लिए किसी प्रसंस्करण की आवश्यकता नहीं है।
दूसरी ओर, दक्षता में अधिकांशतः सुधार होता है यदि अपेक्षाकृत बड़े आधार स्थितियों में पुनरावर्तन को रोक दिया जाता है, और इन्हें गैर-पुनरावर्ती रूप से हल किया जाता है, जिसके परिणामस्वरूप हाइब्रिड एल्गोरिदम होता है। यह रणनीति पुनरावर्ती कॉल के ओवरहेड से बचाती है जो बहुत कम या कोई काम नहीं करती है और विशेष गैर-पुनरावर्ती एल्गोरिदम के उपयोग की अनुमति भी दे सकती है, जो उन आधार स्थितियों के लिए स्पष्ट पुनरावर्तन से अधिक कुशल हैं। सरल हाइब्रिड पुनरावर्ती एल्गोरिथम के लिए सामान्य प्रक्रिया बेस केस को लघु -परिपथ करना है, जिसे आर्म्स-लेंथ रिकर्सन के रूप में भी जाना जाता है। इस मामले में, क्या अगले चरण का परिणाम होगा कि अनावश्यक फ़ंक्शन कॉल से बचने के लिए फ़ंक्शन कॉल से पहले बेस केस की जाँच की जाती है। उदाहरण के लिए, पेड़ में, बच्चे के नोड की पुनरावृत्ति करने के अतिरिक्त और फिर जाँच करें कि क्या यह अशक्त है, पुनरावर्ती से पहले अशक्त जाँच; बाइनरी ट्री पर कुछ एल्गोरिदम में आधे फ़ंक्शन कॉल से बचा जाता है। चूंकि डी एंड सी एल्गोरिदम अंततः प्रत्येक समस्या या उप-समस्या उदाहरण को बड़ी संख्या में आधार उदाहरणों में कम कर देता है, ये अधिकांशतः एल्गोरिदम की समग्र निवेश पर हावी होते हैं, खासकर जब विभाजन/उपरि में सम्मिलित होना कम होता है। ध्यान दें कि ये विचार इस बात पर निर्भर नहीं करते हैं कि संकलक द्वारा या स्पष्ट स्टैक द्वारा पुनरावर्तन प्रयुक्त किया गया है या नहीं।
इस प्रकार, उदाहरण के लिए, सॉर्ट किए जाने वाले आइटमों की संख्या पर्याप्त रूप से कम होने के बाद, क्विकसॉर्ट के कई लाइब्रेरी कार्यान्वयन सरल लूप-आधारित सम्मिलन सॉर्ट (या समान) एल्गोरिथम पर स्विच हो जाएंगे। ध्यान दें कि, यदि खाली सूची एकमात्र आधार मामला था, तो सूची को क्रमबद्ध करना प्रविष्टियां अधिकतम रूप से आवश्यक होंगी क्विकॉर्ट कॉल जो कुछ नहीं करेगी किन्तु तुरंत वापस आ जाएगी। आधार स्थितियों को आकार 2 या उससे कम की सूचियों में बढ़ाने से उनमें से अधिकतर कुछ भी नहीं करने वाले कॉल समाप्त हो जाएंगे, और सामान्यतः 2 से बड़ा आधार मामला सामान्यतः फ़ंक्शन-कॉल ओवरहेड या स्टैक मैनिपुलेशन में बिताए गए समय के अंश को कम करने के लिए उपयोग किया जाता है।
वैकल्पिक रूप से, कोई भी बड़े आधार स्थितियों को नियोजित कर सकता है जो अभी भी विभाजन और जीत एल्गोरिथ्म का उपयोग करते हैं, किन्तु निश्चित आकारों के पूर्व निर्धारित समुच्चय के लिए एल्गोरिथ्म को प्रयुक्त करते हैं जहां एल्गोरिथ्म पूरी तरह से लूप खोलना कोड में हो सकता है जिसमें कोई पुनरावर्तन, लूप या सशर्त (प्रोग्रामिंग) नहीं है। ) (आंशिक मूल्यांकन की विधि से संबंधित)। उदाहरण के लिए, इस दृष्टिकोण का उपयोग कुछ कुशल एफएफटी कार्यान्वयनों में किया जाता है, जहां आधार मामले निश्चित आकार के समुच्चय के लिए डिवाइड-एंड-कॉनकेयर एफएफटी एल्गोरिदम के अनियंत्रित कार्यान्वयन होते हैं।[11] इस रणनीति को कुशलतापूर्वक प्रयुक्त करने के लिए वांछित अलग-अलग आधार स्थितियों की बड़ी संख्या का उत्पादन करने के लिए स्रोत-कोड पीढ़ी विधियों का उपयोग किया जा सकता है।[11]
इस विचार के सामान्यीकृत संस्करण को रिकर्सन अनोलिंग या मोटे होने के रूप में जाना जाता है, और आधार मामले को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव दिया गया है।[12]
अतिव्यापी उप-समस्याओं के लिए गतिशील प्रोग्रामिंग
कुछ समस्याओं के लिए, शाखित पुनरावृत्ति ही उप-समस्या का कई बार मूल्यांकन कर सकती है। ऐसे स्थितियों में इन अतिव्यापी उपसमस्याओं के समाधानों को पहचानने और सहेजने के लायक हो सकता है, विधि को सामान्यतः ज्ञापन के रूप में जाना जाता है। सीमा तक अनुसरण करने पर, यह नीचे-ऊपर डिजाइन | बॉटम-अप डिवाइड-एंड-कॉनकॉर एल्गोरिदम जैसे डायनेमिक प्रोग्रामिंग की ओर जाता है।
यह भी देखें
- एकरा–बाजी विधि
- विघटित एकत्रीकरण फंक्शन
- फोर्क-जॉइन मॉडल
- मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)
- गणितीय प्रेरण
- मानचित्र छोटा करना
- अनुमानी (कंप्यूटर विज्ञान)
संदर्भ
- ↑ Blahut, Richard (14 May 2014). सिग्नल प्रोसेसिंग के लिए फास्ट एल्गोरिदम. Cambridge University Press. pp. 139–143. ISBN 978-0-511-77637-3.
- ↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (31 July 2009). एल्गोरिदम का परिचय. MIT Press. ISBN 978-0-262-53305-8.
- ↑ Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
- ↑ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).
- ↑ 5.0 5.1 5.2 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
- ↑ Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine, 1, (4), 14–21 (1984).
- ↑ Knuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. p. 159. ISBN 0-201-89685-0.
- ↑ Karatsuba, Anatolii A.; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR. 146: 293–294. Translated in Karatsuba, A.; Ofman, Yu. (1963). "Multiplication of Multidigit Numbers on Automata". Soviet Physics Doklady. 7: 595–596. Bibcode:1963SPhD....7..595K.
- ↑ M. Frigo; C. E. Leiserson; H. Prokop (1999). "कैश-बेखबर एल्गोरिदम". Proc. 40th Symp. On the Foundations of Computer Science: 285–297. doi:10.1109/SFFCS.1999.814600. ISBN 0-7695-0409-4. S2CID 62758836.
- ↑ Nicholas J. Higham, "The accuracy of floating-point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).
- ↑ 11.0 11.1 Frigo, M.; Johnson, S. G. (February 2005). "The design and implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.
- ↑ Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs" in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).
