क्या एक रिकर्सिव एल्गोरिदम मौजूद है जो विभाजन में शामिल नहीं होता है और रणनीति जीतता है?

मैं एक एल्गोरिदम की तलाश में हूं जिसे विभाजन का उपयोग करके सुलझाया जा सकता है और रणनीति को जीतने का कारण नहीं है और इसका कारण यह क्यों हल नहीं किया जा सकता है?

0
क्या आप एक समस्या ढूंढ रहे हैं जिसे विभाजित और जीतने के द्वारा हल नहीं किया जा सकता है? या आप एक एल्गोरिदम की तलाश में हैं जो विभाजन और जीत का उपयोग नहीं करता है? अथवा दोनों?
जोड़ा लेखक CompuChip, स्रोत

3 उत्तर

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

एक समस्या के रूप में जिसे विभाजित और जीतने वाली रणनीति का उपयोग करके हल नहीं किया जा सकता है, आप एक अनावश्यक समस्या का सामना कर सकते हैं, जैसे रोकथाम की समस्या, जिसके लिए किसी भी प्रकार का कोई एल्गोरिदम मौजूद नहीं है।

0
जोड़ा
आकार -1 और आकार-एन-1 समस्याओं में एक विभाजन अभी भी एक विभाजन है, हालांकि मैं सहमत हूं कि विभाजन और विजय आम तौर पर लगभग बराबर आकार की समस्याओं में विभाजन को संदर्भित करती है।
जोड़ा लेखक chepner, स्रोत
"परिभाषा के अनुसार, एक पुनरावर्ती एल्गोरिदम एक विभाजित और जीत एल्गोरिदम है" - मुझे यकीन नहीं है कि मैं इसके साथ सहमत हूं। उदाहरण के लिए, मुझे नहीं लगता कि किसी ने कभी गहराई से पहली बार खोज की है- एक विभाजित-और-जीत एल्गोरिदम खोजें। या क्या कोई पूंछ-पुनरावर्ती एल्गोरिदम वर्गीकृत करेगा।
जोड़ा लेखक Dukeling, स्रोत
मुझे लगता है कि अगर यह समस्या दो या दो से अधिक विशिष्ट subproblems में विभाजित है, तो यह केवल विभाजित और जीत है, जिसके परिणामस्वरूप रिकर्सिव कॉल का पेड़ होता है। एक काउंटर उदाहरण फैक्टोरियल है, जो पेड़ की बजाय कॉल की एक श्रृंखला उत्पन्न करता है।
जोड़ा लेखक pjs, स्रोत

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

0
जोड़ा

यह साइट, http://gonitsora.com/algorithm-types-and-classification/, 7 मूल प्रकार के एल्गोरिदम सूचीबद्ध करता है, जिनमें से विभाजित और जीत एक है।

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

Knapsack समस्या एक लालची एल्गोरिदम का उपयोग करता है, और विभाजित और जीत (या तो आधा में knapsack आकार काटने या वस्तुओं को दो हिस्सों में विभाजित करने के द्वारा काम नहीं करेगा। यह उन्हें पुनः संयोजित करने के लिए, गणना, बुद्धिमान, बहुत अधिक खर्च होगा।

0
जोड़ा
किसी समस्या के बीच कोई अंतर नहीं है ज्ञात विभाजन को हल करने के लिए एल्गोरिदम को विभाजित करें और किसी भी विभाजन और जीतने वाले एल्गोरिदम द्वारा समस्या को असफल कर दिया जा सकता है।
जोड़ा लेखक chepner, स्रोत
सहमत हुए, और यह अनजान नहीं था कि मैंने counterexamples के लिए क्लासिक समस्याओं को चुना। मुझे लगता है कि ओपी (या उसका प्रशिक्षक) एक अंतर्ज्ञानी कारण की तलाश में था कि विभाजित और जीत क्यों काम नहीं करेगी, औपचारिक प्रमाण नहीं।
जोड़ा लेखक rajah9, स्रोत