डेटा संरचनाएं - विभाजित और जीतें

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

मोटे तौर पर, हम समझ सकते हैं divide-and-conquer तीन-चरणीय प्रक्रिया में दृष्टिकोण।

फूट डालो / तोड़

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

जीत / समाधान

इस चरण को हल करने के लिए बहुत छोटी उप-समस्याएं प्राप्त होती हैं। आमतौर पर, इस स्तर पर, समस्याओं को अपने दम पर 'हल' माना जाता है।

मर्ज / कम्बाइन

जब छोटी उप-समस्याएं हल हो जाती हैं, तो यह चरण उन्हें पुन: संयोजित करता है जब तक कि वे मूल समस्या का हल नहीं बनाते हैं। यह एल्गोरिदमिक दृष्टिकोण पुनरावर्ती रूप से काम करता है और जीतता है और मर्ज किए गए कदम इतने करीब काम करते हैं कि वे एक के रूप में दिखाई देते हैं।

उदाहरण

निम्नलिखित कंप्यूटर एल्गोरिदम पर आधारित हैं divide-and-conquer प्रोग्रामिंग दृष्टिकोण -

• मर्ज़ सॉर्ट
• जल्दी से सुलझाएं
• द्विआधारी खोज
• स्ट्रैसन की मैट्रिक्स गुणन
• निकटतम जोड़ी (अंक)

कंप्यूटर की किसी भी समस्या को हल करने के लिए विभिन्न तरीके उपलब्ध हैं, लेकिन उल्लिखित विभाजन और विजय दृष्टिकोण का एक अच्छा उदाहरण है।