एक बड़े स्पैस मैट्रिक्स

Question

में "सबसे बड़ा" घना उप मैट्रिक्स खोजें, एक बड़े स्पैर मैट्रिक्स (10k + 1m + द्वारा कहें) को देखते हुए मुझे एक सब्सट्रेट खोजने की आवश्यकता है, जरूरी नहीं कि पंक्तियों और कॉलम जो घने मैट्रिक्स (सभी गैर शून्य तत्व)। मैं चाहता हूं कि यह उप मैट्रिक्स कुछ पहलू अनुपात बाधाओं के भीतर जितना संभव हो उतना बड़ा हो (सबसे बड़ा योग नहीं, बल्कि तत्वों की सबसे बड़ी संख्या)।

क्या इस समस्या के लिए कोई ज्ञात सटीक या अपरिवर्तनीय समाधान है?

Google पर एक त्वरित स्कैन बहुत करीब-करीब-बिल्कुल नतीजे नहीं देता है। मुझे किस शब्द की तलाश करनी चाहिए?

---

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

---

एक चाड Okere के विचार

1. आदेश के आधार पर सोचा छोटी से छोटी गिनती के लिए सबसे बड़ा गिनती से पंक्तियों (आवश्यक नहीं लेकिन पर्फ़ मदद कर सकता है)
2. दो का चयन पंक्तियों है कि एक "बड़े" ओवरलैप
3. अन्य सभी पंक्तियां ओवरलैप को कम नहीं करेंगे
4. रिकार्ड है कि सेट
5. जोड़े जो कुछ भी पंक्ति ov कम कर देता है जोड़े # 3 कम से कम
6. दोहराएँ परिणाम जब तक द्वारा erlap छोटे
जाता # 2 पर पुन: प्रारंभ
7. एक अलग मूल्य उस जोड़ी के साथ जब तक आप तय परिणाम काफी अच्छा

Answer 1

मुझे लगता है कि आप ऐसा कुछ चाहते हैं। आपके पास

1100101 
1110101 
0100101 

आप कॉलम 1,2,5,7 और पंक्तियों 1 और 2 चाहते हैं, है ना? वह submatrix 8 तत्वों के साथ 4x2 होगा। या आप 1,2,7 पंक्तियों के साथ कॉलम 1,5,7 के साथ जा सकते हैं जो 3x3 मैट्रिक्स होगा।

यदि आप 'अनुमानित' विधि चाहते हैं, तो आप एक गैर-शून्य तत्व से शुरू कर सकते हैं, फिर एक और गैर-शून्य तत्व ढूंढने के लिए आगे बढ़ें और पंक्तियों और स्तंभों की अपनी सूची में जोड़ें। किसी बिंदु पर आप एक गैर-शून्य तत्व में भाग लेंगे, यदि आपके संग्रह में पंक्तियां और कॉलम जोड़े गए हैं, तो आपका संग्रह अब पूरी तरह गैर-शून्य नहीं होगा।

तो उपर्युक्त मैट्रिक्स के लिए, यदि आपने 1,1 और 2,2 जोड़े हैं तो आपके संग्रह में 1,2 और कॉलम 1,2 पंक्तियां होंगी। यदि आपने 3,7 जोड़ने की कोशिश की है तो इससे समस्या होगी क्योंकि 1,3 शून्य है। तो आप इसे जोड़ नहीं सकते। हालांकि आप 2,5 और 2,7 जोड़ सकते हैं। 4x2 submatrix बनाना।

आप मूल रूप से पुनरावृति जब तक आप किसी भी अधिक नई पंक्तियों और स्तंभों को जोड़ने के लिए नहीं मिल सकता है जाएगा। इससे आपको स्थानीय न्यूनतम भी मिल जाएगा। आप परिणाम को स्टोर कर सकते हैं और फिर एक और प्रारंभ बिंदु से शुरू कर सकते हैं (शायद वह जो आपके वर्तमान समाधान में फिट नहीं हुआ)।

तब बस रुकें जब आप थोड़ी देर के बाद और नहीं पा सकें।

यही कारण है, जाहिर है, एक लंबा समय लग सकता है, लेकिन मैं नहीं जानता कि यदि आप इसे किसी भी अधिक तेजी से करने में सक्षम हो जाएगा।

Answer 2

संपादित है

जारी रखें। यह नीचे दिए गए समस्या .. मेरे बुरा के रूप में ही नहीं है ...

लेकिन नीचे अंतिम टिप्पणी के आधार पर, यह निम्न के बराबर हो सकता है:

1. शून्य के दूर खड़ी अलग जोड़ी का पता लगाएं अंक जिनके बीच शून्य बिंदु नहीं है।
2. उन शून्य बिंदुओं की सबसे दूर क्षैतिज रूप से अलग जोड़ी खोजें जिनमें उनके बीच कोई शून्य नहीं है?

3. तब क्षैतिज क्षेत्र आप देख रहे हैं आयत कि अंक के इन दो जोड़े के बीच फिट बैठता है?

   इस सटीक समस्या, एक किताब जॉन बेंटले द्वारा "प्रोग्रामिंग मोती" कहा जाता है की एक मणि में चर्चा की है, और, के रूप में मुझे याद है, यद्यपि वहाँ एक आयाम में एक समाधान है, वहाँ के लिए 2-डी या कोई आसान जवाब है उच्च आयामी वेरिएंट ...

1 = D समस्या है, प्रभावी ढंग से, संख्याओं के एक समूह का एक सन्निहित उप-समूह की सबसे बड़ी राशि पाते हैं:

तत्वों के माध्यम से पुनरावृति, एक चल रहा है का ट्रैक रखने एक विशिष्ट पिछले तत्व है, और अधिकतम उप-योग अब तक देखा (और आरंभ और अंत elemnt कि यह generateds) से कुल ...प्रत्येक तत्व पर, यदि अधिकतम उपरोक्त अब तक देखे गए अधिकतम कुल से अधिक है, तो अब तक देखा गया अधिकतम और एंडलेमेंट रीसेट कर दिया गया है ... यदि अधिकतम रनिंग कुल शून्य से नीचे चला जाता है, तो प्रारंभ तत्व वर्तमान तत्व पर रीसेट हो जाता है और रनिंग कुल शून्य पर रीसेट किया गया है ...

2-डी समस्या एक दृश्य छवि प्रसंस्करण एल्गोरिदम उत्पन्न करने के प्रयास से आई, जो खोजने के लिए प्रयास कर रहा था, चमकदार मानों की धारा के भीतर 2-रंगीन छवि में पिक्सेल का प्रतिनिधित्व करता है , छवि के भीतर "चमकदार" आयताकार क्षेत्र खोजें। यानी, चमकदार मूल्यों के उच्चतम योग वाले निहित 2-डी उप-मैट्रिक्स को ढूंढें, जहां "चमक" को पिक्सेल के ब्राइटनेस मान और संपूर्ण छवि की समग्र औसत चमक के बीच अंतर से मापा गया था (इसलिए कई तत्वों के नकारात्मक मान थे)

संपादित करें: 1-डी समाधान को देखने के लिए मैंने इस पुस्तक के दूसरे संस्करण की अपनी प्रतिलिपि बनाई है, और इसमें, जॉन बेंटले का कहना है, "2-डी संस्करण अनसुलझा रहता है क्योंकि यह संस्करण प्रिंट करने के लिए जाता है .. "जो 1 999 में था।

Answer 3

क्या यह Netflix problem है?

MATLAB या कुछ अन्य स्पैर मैट्रिक्स पुस्तकालयों में इसे संभालने के तरीके हो सकते हैं।

क्या आपका अपना इरादा लिखना है?

शायद प्रत्येक पंक्ति के लिए 1 डी दृष्टिकोण आपकी मदद करेगा। प्रत्येक पंक्ति

से अधिक

1. लूप पहले गैर शून्य तत्व
2. के सूचकांक खोजें गैर के बीच सबसे बड़ा अवधि के साथ गैर शून्य पंक्ति तत्व के सूचकांक खोजें: एल्गोरिथ्म इस प्रकार दिखाई देंगे प्रत्येक पंक्ति में शून्य कॉलम और दोनों स्टोर करें।
3. पंक्तियों को गैर-शून्य कॉलम के बीच सबसे छोटे से छोटे अवधि तक क्रमबद्ध करें।

इस बिंदु पर मुझे अस्पष्ट होना शुरू हो रहा है (क्षमा करें, एक एल्गोरिदम डिजाइनर नहीं)। मैं प्रत्येक पंक्ति पर लूपिंग करने की कोशिश करता हूं, शुरुआती बिंदु की अनुक्रमणिका को रेखांकित करता हूं, जो कॉलम इंडेक्स के अधिकतम गैर-शून्य रन की तलाश करता है।

आप निर्दिष्ट नहीं करते हैं कि घने मैट्रिक्स को वर्ग होना चाहिए या नहीं। मैं नहीं मानूंगा।

मुझे नहीं पता कि यह कितना कुशल है या इसका बिग-ओ व्यवहार क्या होगा। लेकिन यह शुरू करने के लिए एक क्रूर बल विधि है।

Answer 4

मैं तुम्हें अब इस पर काम नहीं कर रहे हैं, लेकिन मैंने सोचा था कि भविष्य में कोई मुझे के रूप में ही सवाल हो सकता है।

तो, यह साकार करने के बाद एक एनपी कठिन समस्या (मैक्स-गुट को कम करने के द्वारा) मैं एक अनुमानी कि अब तक मेरे लिए अच्छी तरह से काम किया है के साथ आने का फैसला किया:

को देखते हुए एक एन एक्स

भाग: एम द्विआधारी/बूलियन मैट्रिक्स, एक बड़े घने submatrix लगता है उत्पन्न उचित उम्मीदवार submatrices

1. एन पंक्तियों में से प्रत्येक के एक एम आयामी द्विआधारी वेक्टर होने के लिए विचार करें, v_i, जहां मैं = 1 गणना करने के लिए एन
2. आलोचनात्मक अंतर का उपयोग कर एन वैक्टर के लिए एक दूरी मैट्रिक्स
3. में से प्रत्येक के उपयोग UPGMA (समांतर माध्य साथ अनिर्धारित जोड़ी समूह विधि) क्लस्टर वैक्टर करने के लिए एल्गोरिथ्म

प्रारंभ में, v_i वैक्टर एक सिंगलटन क्लस्टर है। उपरोक्त चरण 3 (क्लस्टरिंग) ऑर्डर देता है कि वैक्टर को सबमिटरिस में जोड़ा जाना चाहिए। तो पदानुक्रमित क्लस्टरिंग पेड़ में प्रत्येक आंतरिक नोड एक उम्मीदवार submatrix है।

भाग द्वितीय: स्कोर और रैंक उम्मीदवार submatrices

1. प्रत्येक submatrix के लिए, गणना डी, एक के साथ किसी भी स्तंभ को नष्ट करने से submatrix के लिए वैक्टर के घने सबसेट में तत्वों की संख्या या अधिक शून्य
2. submatrix कि अधिकतम का चयन करें डी

मैं भी प्रारंभिक पूर्ण मैट्रिक्स से संरक्षित किया जा करने के लिए आवश्यक है कि पंक्तियों की न्यूनतम संख्या के बारे में कुछ बातों को किया था, और मैं किसी भी उम्मीदवार submatrices कि पूरा नहीं किया छोड़ दिए जाएंगे अधिकतम डी मान के साथ एक submatrix का चयन करने से पहले यह मानदंड।