छोटी से छोटी सेट समूह के सभी combinatory संभावनाओं

Question

मैं साहचर्य एल्गोरिथ्म पर कुछ अभ्यास कर रही हूँ और नीचे दिए गए प्रश्न हल करने के लिए कैसे पता लगाने की कोशिश कवर करने के लिए खोजें:

25 बिट्स के एक समूह, सेट को देखते हुए (चयन) 15 (गैर permutable और व्यवस्था गैर मामलों):

n!/(k!(n-k)!) = 3.268.760 

अब इन संभावनाओं के हर एक मैट्रिक्स जहां मैं कहाँ में के बीच यह वहाँ पर होना चाहिए के संबंध में अन्य सभी 25bit सदस्य के खिलाफ हर अद्वितीय 25bit सदस्य पार निर्माण के लिए

कम से कम 11 आम निर्धारित बिट्स (केवल एक, शून्य नहीं)।

मुझे बाइनरी डेटा के रूप में यह प्रतिनिधित्व करने को वर्णन करने की कोशिश करते हैं, तो पहला सदस्य होगा:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits) 
0000000001011111111111111 second member 
0000000001101111111111111 third member 
0000000001110111111111111 and so on.... 
... 
1111111111111110000000000 up to here. The 3.268.760 member. 

अब 1 x 1 के लिए एक मैट्रिक्स मैं 15 बिट्स आम होना आवश्यक है पर इन मूल्यों को पार। चूंकि परिणाम है> = 11 यह एक "उपयोगी" परिणाम है।

1 एक्स 2 के लिए हमारे पास 14 बिट्स आम हैं, इसलिए एक वैध परिणाम भी है।

ऐसा करने के लिए, सभी सदस्यों के लिए, आखिरकार, 1 x 3.268.760 को पार करने के परिणामस्वरूप 5 बिट सामान्य हो सकते हैं क्योंकि यह < 11 है, यह "उपयोगी" नहीं है।

मुझे क्या चाहिए (गणित या एल्गोरिदम द्वारा) जो कि 11 बिट्स सामान्य होने वाली सभी संभावनाओं को कवर करने के लिए आवश्यक सदस्यों की न्यूनतम संख्या है।

दूसरे शब्दों में एन सदस्यों का एक समूह जो कि अन्य सभी के खिलाफ परीक्षण किया गया है, में कुल 3.268.760 x 3.268.760 ब्रह्मांड में कम से कम 11 बिट्स हो सकते हैं।

एक ब्रूट फोर्स एल्गोरिदम का उपयोग करके मुझे पता चला कि 81 25 बिट सदस्य के साथ यह संभव है। लेकिन मुझे लगता है कि यह संख्या छोटा होना चाहिए (12 के करीब कुछ)।

मैं 3.268.760 पर 12 सदस्यों की सभी संभावित विविधताओं को बनाने के लिए एक ब्रूट फोर्स एल्गोरिदम का उपयोग करने की कोशिश कर रहा था लेकिन संभावनाओं की संख्या इतनी बड़ी है कि गणना करने में सौ से अधिक वर्षों लगेंगे (3,156x10e69 संयोजन)।

मैंने संयोजक के बारे में गुमराह किया है लेकिन ऐसे कई क्षेत्र हैं जिन्हें मैं नहीं जानता कि इन समस्याओं को फिट होना चाहिए।

तो संयोजन के विच क्षेत्र पर किसी भी दिशा, या इन मुद्दों के लिए किसी भी एल्गोरिदम की सराहना की जाती है।

पीएस: बस संदर्भ के लिए। दो सदस्यों के "समानता" का उपयोग कर की गणना:

(Not(a xor b)) and a 

उसके बाद आम बिट्स की संख्या को देखते हुए बिट्स गिनती करने के लिए एक छोटा सा पुनरावर्ती पाश नहीं है।

संपादित करें: टिप्पणी पर (@btilly) promissed के रूप में यहाँ नीचे 'भग्न' संबंधों या link to image

रंग पैमाने हरे रंग के लाल (15bits मैच) से लेकर की छवि है (11bits मैच) 10 बिट से कम मूल्यों के लिए काला करने के लिए।

यह छवि केवल 4096 प्रथम समूहों का नमूना है।

Answer 1

इस प्रकार की समस्या बेहद कठिन है, आपको सटीक उत्तर खोजने में सक्षम होने की उम्मीद नहीं करनी चाहिए।

एक लालची समाधान को "काफी अच्छा" जवाब देना चाहिए। लेकिन ... लालची कैसे हो?

विचार हमेशा अगले तत्व को चुनने के लिए है जो कि कई संभावनाओं से मेल खाता है जो आप वर्तमान में बेजोड़ हो सकते हैं। दुर्भाग्यवश 3 मिलियन से अधिक संभावित सदस्यों के साथ, आपको लाखों बेजोड़ सदस्यों के खिलाफ मिलान करने की कोशिश करनी है (ध्यान दें, आपका सबसे अच्छा अगला अनुमान आपके उम्मीदवार सेट में पहले से ही किसी अन्य सदस्य से मिल सकता है ..), यहां तक ​​कि यह भी चुनना कि अगला तत्व शायद संभव नहीं है।

तो हमें अगले तत्व को चुनने के बारे में लालची होना होगा। हम वर्तमान में बेजोड़ तत्वों के अंततः मिलान करने की संभावनाओं के योग को अधिकतम करने के लिए प्रत्येक बिट का चयन करेंगे।

कि के लिए हम एक 2-आयामी लुकअप तालिका P ऐसी है कि P(n, m) संभावना है कि दो यादृच्छिक सदस्यों, आम में कम से कम 11 बिट के लिए बाहर हो जाएगा है की आवश्यकता होगी, तो पहले n बिट्स कि में 1 हैं m पहले सदस्य दूसरे में भी 1 हैं। 225 संभावनाओं की यह तालिका प्रीकंप्यूटेड होनी चाहिए।

इस तालिका में आसानी से निम्नलिखित नियमों का उपयोग कर की जा सकती है:

1. P(15, m) 0 है अगर m < 11, 1 अन्यथा।

2. n < 15 के लिए:

   P(n, m) = P(n+1, m+1) * (15-m)/(25-n) + P(n+1, m) * (10-n+m)/(25-n) 
   

अब चलो कुछ सदस्यों को बताया कि कर रहे हैं "बहुत दूर" एक दूसरे से साथ शुरू करते हैं। मेरे सुझाव होगा:

1. पहले 15 बिट्स 1, बाकी 0.
2. पहले 10 बिट 0, बाकी 1.
3. पहले 8 बिट 1, पिछले 7 1, बाकी 0.
4. बिट्स 1 -4, 9-12, 16-23 1, बाकी 0.

अब आपके ब्रह्मांड (25 चुनिंदा 15) सदस्यों से शुरू हो रहा है, उन सभी को खत्म करें जो आपके प्रारंभिक संग्रह में तत्वों में से किसी एक से मेल खाते हैं।

अगला हम एल्गोरिदम के दिल में जाते हैं।

While there are unmatched members: 
    Find the bit that appears in the most unmatched members (break ties randomly) 
    Make that the first set bit of our candidate member for the group. 
    While the candidate member has less than 15 set bits: 
     Let p_best = 0, bit_best = 0; 
     For each unset bit: 
      Let p = 0 
      For each unmatched member: 
       p += P(n, m) where m = number of bits in common between 
          candidate member+this bit and the unmatched member 
          and n = bits in candidate member + 1 
      If p_best < p: 
       p_best = p 
       bit_best = this unset bit 
     Set bit_best as the next bit in our candidate member. 
    Add the candidate member to our collection 
    Remove all unmatched members that match this from unmatched members 
The list of candidate members is our answer 

मैंने कोड नहीं लिखा है, इसलिए मुझे नहीं पता कि इस एल्गोरिदम का जवाब कितना अच्छा होगा। लेकिन यह मानते हुए कि यह आपके वर्तमान से बेहतर नहीं है, 77 उम्मीदवारों के सदस्यों के लिए (हमने धोखा दिया और 4 से शुरू किया) आपको अपने बेजोड़ उम्मीदवारों के माध्यम से 271 पास करना होगा (25 पहली बार ढूंढने के लिए, दूसरे को ढूंढने के लिए 24, इत्यादि) 11 मिलान करने वाले सदस्यों को हटाने के लिए 15 वें और एक और को खोजने के लिए)। यह 20867 पास है। यदि आपके पास औसतन 1 मिलियन बेजोड़ सदस्य हैं, तो यह 20 अरब परिचालन के आदेश पर है।

यह तेज़ नहीं होगा। लेकिन यह कम्प्यूटेशनल रूप से व्यवहार्य होना चाहिए।

Answer 2

टीएल; डॉ: आप dominating set को एक बड़े, अत्यंत सममित ग्राफ पर हल करना चाहते हैं।बिलकुल सही है कि आपको सटीक उत्तर की उम्मीद नहीं करनी चाहिए। अगर यह मेरी समस्या थी, तो मैं लालची समाधान से शुरू होने वाली स्थानीय खोज की कोशिश करूंगा। एक सेट उठाओ और दूसरों को बदलकर इसे छुटकारा पाने का प्रयास करें। इस डेटा को ट्रैक रखने के लिए डेटा संरचनाओं की आवश्यकता होती है कि कौन से सेट बिल्कुल एक बार कवर किए जाते हैं।

संपादित करें: ठीक है, यहां निचले बाउंड के लिए एक बेहतर विचार है। इष्टतम समाधान के 1 से प्रत्येक के लिए प्रत्येक के लिए, [25 चुनें 15] * के/[के सेट के अधिकतम संयुक्त कवरेज] की निचली सीमा है। 12 की आपकी सीमा (वास्तव में 10 मेरी गणना के अनुसार, क्योंकि आप कुछ पड़ोसियों को भूल गए हैं) के = 1 के अनुरूप है। प्रूफ स्केच: एम सेट के साथ एक मनमानी समाधान को ठीक करें और एम के द्वारा प्राप्त किए जा सकने वाले सबसे अधिक कवरेज पर विचार करें। एक आंशिक समाधान बनाएं जहां चुने गए के सभी समरूपता एक साथ औसत और स्केल हो जाएं ताकि प्रत्येक तत्व एक बार कवर हो। इस समाधान की लागत [25 चुनिंदा 15] * के/[उन के सेटों का अधिकतम संयुक्त कवरेज] है, जो कम से कम उतनी ही बड़ी है जितनी हम शूटिंग कर रहे हैं। हालांकि, यह अभी भी कम से कम छोटा है, मूल एम-सेट समाधान के रूप में, क्योंकि प्रत्येक सेट के सीमांत रिटर्न कम हो रहे हैं।

अधिकतम कवरेज कंप्यूटिंग सामान्य रूप से कठिन है, लेकिन एक कारक (ई/(ई -1)) - अनुमान (≈ 1.58) एल्गोरिदम है: लालची, जो ऐसा लगता है जैसे आप जल्दी से कार्यान्वित कर सकते हैं (नोट: आपको इसकी आवश्यकता है उस सेट का चयन करें जिसमें प्रत्येक बार सबसे अनदेखा अन्य सेट शामिल हों)। ई/(ई -1) द्वारा लालची समाधान को गुणा करके, हम के तत्वों के अधिकतम कवरेज पर ऊपरी बाउंड प्राप्त करते हैं, जो पिछले पैराग्राफ में वर्णित निचली बाउंड को शक्ति देने के लिए पर्याप्त है।

चेतावनी: यदि यह ऊपरी सीमा [25 चुनने 15] से बड़ा है, तो के बहुत बड़ा है!