मेरे पास मनमाने ढंग से सेट (नीचे बिंदु) हैं, और मनमाने ढंग से (नीचे ए-सी) में कुछ श्रेणियां ओवरलैपिंग हैं। परीक्षण यह निर्धारित करना है कि प्रत्येक आइटम को एकल श्रेणी में असाइन किया जा सकता है, जिसमें से पहले से संबंधित है, जैसे कि प्रत्येक श्रेणी कम से कम कुछ आइटमों के साथ समाप्त होती है।ओवरलैपिंग श्रेणियों में वस्तुओं को अलग करने के लिए ब्रूट फोर्स की तुलना में बेहतर एल्गोरिदम क्या है?
तो उदाहरण के लिए, हमें ए, बी, और सी की आवश्यकता हो सकती है प्रत्येक दावा एक आइटम। अगर हमें नीचे दिए गए सभी 4 बिंदु दिए गए हैं, यह दिखाते हुए कि यह संभव है, यह आसान है: केवल सभी वस्तुओं को एक सूची में चिपकाएं, श्रेणियों के माध्यम से लूप करें, और प्रत्येक श्रेणी में उस आइटम को हटा दें जिसके पास इसका उपयोग है, और जब तक प्रत्येक श्रेणी एक आइटम को हटाने में सक्षम है, हम परीक्षण पास करते हैं।
अब हम नीले डॉट को हटाने और परीक्षण दोहराने लगता है। स्पष्ट रूप से हम पीले से ए, लाल से बी, और हरे से सी को असाइन कर सकते हैं, और फिर हम पास हो जाते हैं। लेकिन इस समाधान को संहिताबद्ध करना मुश्किल है: यदि हम पिछली विधि का पालन करते हैं (फिर कोई नीला बिंदु नहीं), तो मान लें कि ए हरे रंग के बिंदु को हटाकर शुरू होता है। अब यदि बी पीले बिंदु को हटा देता है, तो हम परीक्षण में असफल हो जाएंगे (चूंकि सी लाल बिंदु को हटा नहीं सकता है), जबकि यदि बी लाल डॉट को हटा देता है, सी अभी भी पीला और पास ले सकता है।
कोई भी श्रेणियों में वस्तुओं के हर संभव असाइनमेंट के माध्यम से इसे बलपूर्वक बलपूर्वक हल कर सकता है, यह देखने के लिए कि प्रत्येक पुनरावृत्ति के साथ स्थिति पूरी हो जाती है, लेकिन यह वस्तुओं और श्रेणियों की मनमानी संख्याओं के लिए अच्छी तरह से स्केल नहीं करेगा, और मुझे लगता है कि एक स्मार्ट या अधिक कुशल तरीका है।
मुझे इस समस्या का नाम नहीं पता है, जिससे अनुसंधान करना मुश्किल हो जाता है। क्या इसका इष्टतम समाधान है? यदि हां, तो समाधान के लिए मैं किस तरह की जटिलता की उम्मीद कर सकता हूं?
मैंने इसे पूरी तरह से नहीं सोचा है, लेकिन ऐसा लगता है कि इसे गतिशील प्रोग्रामिंग दृष्टिकोण के साथ हल करने योग्य होना चाहिए, और इस प्रकार ज्ञापन से बहुत लाभ होता है। –
मुझे समस्या की औपचारिक प्रकृति को समझना मुश्किल लगता है। क्या आपका मतलब है "प्रत्येक आइटम को एक ही श्रेणी में * के लिए असाइन किया जाना चाहिए * जिसमें से प्रत्येक श्रेणी * कम से कम किसी दिए गए * आइटमों के साथ समाप्त होती है"? –
@GiulioFranco, बिल्कुल, – Shep