एल्गोरिथम डिज़ाइन प्रतिमान
एल्गोरिथम डिज़ाइन प्रतिमान उच्च-स्तरीय रणनीतियाँ हैं जो बार-बार उपयोग की जाती हैं — जैसे डिवाइड-एंड-कॉन्कर (विभाजित करो और जीतो), डायनेमिक प्रोग्रामिंग (गत्यात्मक प्रोग्रामिंग), ग्रीडी चॉइस (लालची चुनाव), और प्रूनिंग (छंटाई) के साथ संपूर्ण खोज — ताकि कम्प्यूटेशनल समस्याओं के लिए सही और कुशल एल्गोरिथम का निर्माण किया जा सके।
Definition
एक एल्गोरिथम डिज़ाइन प्रतिमान समस्याओं के एक वर्ग को हल करने के लिए एक सामान्य टेम्पलेट या रणनीति है, जिसकी विशेषता समस्या को विघटित करने और उप-समाधानों को संयोजित करने का एक तरीका है, साथ ही वे संरचनात्मक गुण जो समस्या में होने चाहिए ताकि प्रतिमान लागू हो सके।
Scope
यह क्षेत्र किसी एक समस्या डोमेन से स्वतंत्र एल्गोरिथम बनाने के लिए सामान्य-उद्देश्य वाली तकनीकों को शामिल करता है। यह बताता है कि किसी समस्या की संरचना (इष्टतम उप-संरचना, अतिव्यापी उप-समस्याएँ, लालची-चुनाव गुण, विघटनशीलता) कैसे एक मिलान रणनीति का सुझाव देती है, और प्रत्येक प्रतिमान की शुद्धता के लिए कैसे तर्क दिया जाता है और चलने के समय के लिए विश्लेषण किया जाता है। इसमें इन एल्गोरिथम को लागू करने वाली डेटा संरचनाएँ (मौलिक डेटा संरचनाओं में शामिल) और किसी भी एल्गोरिथम द्वारा प्राप्त की जा सकने वाली जटिलता-सैद्धांतिक सीमाएँ (जटिलता और एल्गोरिथम के विश्लेषण में शामिल) शामिल नहीं हैं।
Sub-topics
Core questions
- किसी समस्या का कौन सा संरचनात्मक गुण किसी दिए गए प्रतिमान को लागू करने योग्य और सही बनाता है?
- मेमोइज़ेशन या टैबुलेशन के माध्यम से एक पुनरावर्ती अपघटन को एक कुशल एल्गोरिथम में कैसे बदला जाता है?
- एक स्थानीय रूप से इष्टतम (लालची) चुनाव कब विश्व स्तर पर इष्टतम समाधान की ओर ले जाता है?
- एक प्रतिमान-आधारित एल्गोरिथम का चलने का समय कैसे प्राप्त किया जाता है, उदा. पुनरावृत्तियों के माध्यम से?
- संपूर्ण-खोज प्रतिमान विशिष्ट उदाहरणों पर व्यवहार्य बने रहने के लिए खोज स्थान को कैसे छाँटते हैं?
Key concepts
- डिवाइड-एंड-कॉन्कर
- पुनरावृत्ति संबंध
- डायनेमिक प्रोग्रामिंग
- मेमोइज़ेशन और टैबुलेशन
- लालची चुनाव और विनिमय तर्क
- बैकट्रैकिंग
- ब्रांच एंड बाउंड
- इष्टतम उप-संरचना
- संपूर्ण खोज और छंटाई
Key theories
- इष्टतम उप-संरचना
- किसी समस्या में इष्टतम उप-संरचना तब होती है जब एक इष्टतम समाधान को उसके उप-समस्याओं के इष्टतम समाधानों से इकट्ठा किया जा सकता है; यह गुण डायनेमिक प्रोग्रामिंग और कई लालची एल्गोरिथम दोनों का आधार है।
- अतिव्यापी उप-समस्याएँ और मेमोइज़ेशन
- जब एक पुनरावर्ती अपघटन बार-बार एक ही उप-समस्याओं को दोहराता है, तो प्रत्येक उप-समस्या के समाधान को संग्रहीत करना (मेमोइज़ेशन या बॉटम-अप टैबुलेशन) घातीय पुनर्गणना को बहुपद समय तक कम कर देता है — जो डायनेमिक प्रोग्रामिंग का आधार है।
- लालची-चुनाव गुण
- कुछ समस्याएँ एक विश्व स्तर पर इष्टतम समाधान स्वीकार करती हैं जो उस चुनाव को बार-बार करके बनाया जाता है जो उस समय सबसे अच्छा लगता है; शुद्धता आमतौर पर एक विनिमय तर्क या मैट्रोइड सिद्धांत के माध्यम से सिद्ध की जाती है।
Clinical relevance
डिज़ाइन प्रतिमान व्यावहारिक सॉफ्टवेयर की कार्यशील शब्दावली हैं: डिवाइड-एंड-कॉन्कर तेज़ सॉर्टिंग और सिग्नल प्रोसेसिंग का आधार है, डायनेमिक प्रोग्रामिंग बायोइन्फॉर्मेटिक्स में अनुक्रम संरेखण और सबसे छोटे-पथ के सबराउटिन को शक्ति प्रदान करती है, ग्रीडी विधियाँ शेड्यूलिंग और डेटा कम्प्रेशन (हफमैन कोडिंग) को संचालित करती हैं, और ब्रांच-एंड-बाउंड कॉम्बिनेटरियल ऑप्टिमाइजेशन और ऑपरेशंस रिसर्च के लिए केंद्रीय है।
History
डिवाइड-एंड-कॉन्कर तर्क कंप्यूटरों से पहले का है, लेकिन 1960 के दशक में मर्जसॉर्ट और करात्सुबा गुणन जैसे तेज़ एल्गोरिथम के साथ केंद्रीय बन गया। रिचर्ड बेलमैन ने 1950 के दशक में डायनेमिक प्रोग्रामिंग की शुरुआत की। प्रतिमानों का एक एकीकृत लेंस के रूप में व्यवस्थित पाठ्यपुस्तक उपचार अहो, हॉपक्रॉफ्ट और उल्मैन के डिज़ाइन-एंड-एनालिसिस टेक्स्ट और बाद में CLRS और क्लेनबर्ग-टार्डोस जैसे कार्यों के माध्यम से परिपक्व हुआ।
Key figures
- Richard Bellman
- Thomas H. Cormen
- Jon Kleinberg
- Éva Tardos
- Robert Sedgewick
Related topics
Seminal works
- cormen2009
- kleinberg2006
- sedgewick2011
Frequently asked questions
- डायनेमिक प्रोग्रामिंग और लालची एल्गोरिथम के बीच क्या अंतर है?
- दोनों इष्टतम उप-संरचना का लाभ उठाते हैं, लेकिन एक लालची एल्गोरिथम प्रत्येक चरण में एक स्थानीय रूप से इष्टतम चुनाव के लिए प्रतिबद्ध होता है और उस पर कभी पुनर्विचार नहीं करता है, जबकि डायनेमिक प्रोग्रामिंग सभी प्रासंगिक उप-समस्याओं के समाधानों पर विचार करती है और उन्हें जोड़ती है। जब यह लागू होता है तो लालची एल्गोरिथम तेज़ होता है लेकिन कम समस्याओं के लिए सही होता है।
- मुझे कैसे पता चलेगा कि किस प्रतिमान का उपयोग करना है?
- समस्या की संरचना को देखें: स्वतंत्र उप-समस्याओं में विघटित होने से डिवाइड-एंड-कॉन्कर का सुझाव मिलता है; इष्टतम उप-संरचना के साथ अतिव्यापी उप-समस्याएँ डायनेमिक प्रोग्रामिंग का सुझाव देती हैं; एक सिद्ध लालची-चुनाव गुण एक लालची एल्गोरिथम का सुझाव देता है; और अन्यथा छंटाई (बैकट्रैकिंग या ब्रांच-एंड-बाउंड) के साथ व्यवस्थित खोज की आवश्यकता हो सकती है।