एल्गोरिथ्म: आदेश नहीं सबसेट लागू करने के लिए

Question

मैं एक समस्या जो मुझे हल करने के लिए पता नहीं कैसे मिल गया में एक सेट से संभव के रूप में कुछ तत्व हटाना:

मैं सेट A = {A_1, A_2, ..., A_n} का एक सेट है और मैं एक सेट है B ।

अब लक्ष्य से B (B' बनाने) संभव के रूप में कुछ तत्वों को दूर करने, ऐसा है कि, सभी 1 <= i <= n के लिए तत्वों को निकालने के बाद, A_iनहींB' के एक सबसेट है।

उदाहरण के लिए, यदि हमारे पास A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5}, और B={1,2,3,4,5} है, तो हम उदा। B से 1 और 2 को हटा दें (जो B'={3,4,5} उत्पन्न करेगा, जो A_i में से एक का सुपरसेट नहीं है)।

क्या निकालने के लिए (न्यूनतम संख्या) तत्वों को निर्धारित करने के लिए कोई एल्गोरिदम है?

Answer 1

ऐसा लगता है कि आप B से A के न्यूनतम hitting set को हटाना चाहते हैं (यह कशेरुक कवर समस्या से निकटता से संबंधित है)।

कुछ सेट-ऑफ-सेट A के लिए एक सेट सेट स्वयं एक सेट है जिसमें A में प्रत्येक सेट से कम से कम एक तत्व होता है (यह प्रत्येक सेट "हिट" करता है)। न्यूनतम मारने वाला सेट सबसे छोटा हिट सेट है। इसलिए, यदि आपके सेट-ऑफ-सेट A के लिए एमएचएस है, तो आपके पास प्रत्येक सेट से A में एक तत्व है। B से इसे हटाने का अर्थ है A में कोई सेट B का उप-समूह हो सकता है।

तुम सब करने की ज़रूरत के लिए MHS गणना है (, एक एक , ... एक _n), तो हटा दें कि B से। दुर्भाग्यवश, एमएचएस ढूंढना एक एनपी-पूर्ण समस्या है। यह जानते हुए कि हालांकि, आप कुछ ही विकल्प हैं:

1. अपने डेटा सेट छोटी है, तो स्पष्ट जानवर बल समाधान
2. उपयोग एक तेज, अनुमानित जवाब पाने के लिए एक संभाव्य एल्गोरिथ्म करना (देखें this PDF)
3. दूर भागें, विपरीत दिशा में दूर

Answer 2

मुझे लगता है कि आपको इन सेटों से न्यूनतम लंबाई मिलनी चाहिए और फिर इस सेट में मौजूद इन तत्वों को हटा दें।

Answer 3

यदि आपको केवल कुछ अनुमान की आवश्यकता है, तो ए में सबसे छोटे सेट से शुरू करें, और बी से एक तत्व हटा दें (आप केवल यादृच्छिक रूप से एक को पकड़ सकते हैं, या यह देखने के लिए जांच सकते हैं कि ए में सबसे अधिक सेट में कौन सा तत्व है, कितनी सटीक, आपको कितनी तेज़ी से आवश्यकता है)

अब ए में सबसे छोटा सेट बी से ऊपर नहीं है, लेकिन वहां से पहले यह जांचने के लिए जांचें कि आप जिन सेटों की जांच कर रहे हैं, वे इस पर सबसेट हैं या नहीं बिंदु या नहीं।

यह मुझे कशेरुक समस्या को हल करने की याद दिलाता है, और मुझे इसके लिए कुछ अनुमानित एल्गोरिदम याद है जो इस के समान है।