DAA - विभाजित और जीतें
कई एल्गोरिदम प्रकृति में पुनरावर्ती हैं जो किसी दिए गए समस्या को हल करने के लिए पुनरावर्ती रूप से उप-समस्याओं से निपटते हैं।
में divide and conquer approach, एक समस्या को छोटी समस्याओं में विभाजित किया जाता है, फिर छोटी समस्याओं को स्वतंत्र रूप से हल किया जाता है, और अंत में छोटी समस्याओं के समाधान को बड़ी समस्या के समाधान में जोड़ा जाता है।
आम तौर पर, डिवाइड-एंड-कॉनकोर एल्गोरिदम के तीन भाग होते हैं -
Divide the problem उप-समस्याओं की संख्या में जो एक ही समस्या के छोटे उदाहरण हैं।
Conquer the sub-problemsउन्हें पुन: हल करके। यदि वे काफी छोटे हैं, तो उप-समस्याओं को आधार मामलों के रूप में हल करें।
Combine the solutions मूल समस्या के समाधान में उप-समस्याओं के लिए।
फूट डालो और जीतो दृष्टिकोण के पेशेवरों और विपक्ष
विभाजित और जीतना दृष्टिकोण समानता का समर्थन करता है क्योंकि उप-समस्याएं स्वतंत्र हैं। इसलिए, एक एल्गोरिथ्म, जिसे इस तकनीक का उपयोग करके बनाया गया है, मल्टीप्रोसेसर सिस्टम पर या एक साथ विभिन्न मशीनों में चल सकता है।
इस दृष्टिकोण में, अधिकांश एल्गोरिदम को पुनरावृत्ति का उपयोग करके डिज़ाइन किया गया है, इसलिए स्मृति प्रबंधन बहुत अधिक है। पुनरावर्ती फ़ंक्शन स्टैक के लिए उपयोग किया जाता है, जहां फ़ंक्शन स्थिति को संग्रहीत करने की आवश्यकता होती है।
फूट डालो और जीतो का आवेदन
निम्नलिखित कुछ समस्याएं हैं, जो विभाजित और विजय दृष्टिकोण का उपयोग करके हल की जाती हैं।
- संख्याओं के अनुक्रम का अधिकतम और न्यूनतम ज्ञात करना
- स्ट्रैसेन का मैट्रिक्स गुणन
- मर्ज़ सॉर्ट
- द्विआधारी खोज