एक बाइनरी 2 डी मैट्रिक्स छंटनी?

Question

मैं यहां कुछ पॉइंटर्स ढूंढ रहा हूं क्योंकि मुझे नहीं पता कि यह कहां से शुरू करना है।

मैं जैसे, प्रत्येक कोशिका में 0 या 1 के साथ एक 2 डी मैट्रिक्स है:

1 2 3 4 
A 0 1 1 0 
B 1 1 1 0 
C 0 1 0 0 
D 1 1 0 0 

और इसलिए यह "ऊपरी त्रिकोणीय" संभव के रूप में है, इसलिए की तरह के रूप में है मैं इसे सुलझाने के लिए करना चाहते हैं:

4 3 1 2 
B 0 1 1 1 
A 0 1 0 1 
D 0 0 1 1 
C 0 0 0 1 

पंक्तियां और कॉलम बरकरार रहना चाहिए, यानी तत्वों को व्यक्तिगत रूप से स्थानांतरित नहीं किया जा सकता है और केवल "संपूर्ण" को बदला जा सकता है।

मैं समझता हूँ कि शायद रोग मामलों में जहां एक मैट्रिक्स कई संभव क्रमबद्ध परिणाम है हो जाएगा (यानी एक ही आकार है, लेकिन "मूल" पंक्तियों/स्तंभों की पहचान में मतभेद है।)

तो, किसी को भी यह कर सकते हैं सुझाव है कि मुझे इसके लिए कुछ शुरुआती बिंदु कहां मिल सकते हैं? एक मौजूदा लाइब्रेरी/एल्गोरिदम बहुत अच्छा होगा, लेकिन मैं उस समस्या का नाम जानने के लिए बसूंगा जिसे मैं हल करने की कोशिश कर रहा हूं!

मुझे संदेह है कि यह एक रैखिक बीजगणित समस्या है, और हो सकता है कि कुछ प्रकार की छवि प्रसंस्करण तकनीक लागू हो।

किसी भी अन्य विचारों को एक तरफ, मेरी प्रारंभिक अनुमान सिर्फ पंक्तियों पर कॉलम शामिल करनी तरह लिखने के लिए है, तो और पुनरावृति जब तक यह स्थिर है कि है (और उम्मीद है कि रोग के मामलों का पता लगाने के बहुत कठिन नहीं है।)

अधिक जानकारी: मैं जो करने की कोशिश कर रहा हूं उस पर कुछ और जानकारी स्पष्ट करने में मदद कर सकती है। प्रत्येक पंक्ति एक प्रतियोगी का प्रतिनिधित्व करती है, प्रत्येक कॉलम एक चुनौती का प्रतिनिधित्व करता है। प्रत्येक 1 या 0 किसी विशेष चुनौती पर प्रतिद्वंद्वी के लिए "सफलता" का प्रतिनिधित्व करता है।

मैट्रिक्स को सॉर्ट करके सभी 1s शीर्ष-दाएं में हैं, इसलिए मुझे उम्मीद है कि प्रत्येक चुनौती की आंतरिक कठिनाई और प्रतिस्पर्धियों की रैंकिंग (जो चुनौतियों की कठिनाई को ध्यान में रखेगी) सफलताओं की संख्या में सफल नहीं हुआ।)

स्वीकृत उत्तर पर नोट: मैंने चेतावनी के साथ "उत्तर" के रूप में नकली एनीलिंग को स्वीकार किया है कि इस प्रश्न का सही उत्तर नहीं है। यह एक अच्छा दृष्टिकोण की तरह लगता है, हालांकि मैं वास्तव में एक स्कोरिंग समारोह के साथ आने में कामयाब नहीं रहा हूं जो मेरी समस्या के लिए काम करता है। एक नंबर

क्रमबद्ध अवरोही क्रम में संख्या में दोहरे बीट्स से

Convert प्रत्येक पंक्ति:

Answer 1

simulated annealing पर आधारित एक एल्गोरिदम बहुत अधिक परेशानी के बिना इस तरह की चीज़ को संभाल सकता है। बहुत अच्छा नहीं है यदि आपके पास छोटी मैट्रिक्स हैं जो संभवतः एक निश्चित समाधान है, लेकिन यदि आपके मैट्रिक्स बड़े हो जाते हैं और समस्या अधिक कठिन हो जाती है तो बहुत अच्छा होता है।

(हालांकि, यह भी अपनी इच्छा है कि सम्मिलन संवर्द्धित किया जा सकता है विफल रहता है।)

प्रारंभिक

1. एक प्रदर्शन समारोह वसीयत है कि "स्कोर" एक मैट्रिक्स - मैट्रिक्स कि के करीब हैं आपकी त्रिभुज कम त्रिकोण-वाई की तुलना में बेहतर स्कोर प्राप्त करनी चाहिए।

2. मैट्रिक्स पर की अनुमतियों का एक सेट तैयार करें। आपका विवरण थोड़ा अस्पष्ट था, लेकिन यदि आप पंक्तियों को स्वैप कर सकते हैं तो एक सेशन SwapRows(a, b) होगा। एक और SwapCols(a, b) हो सकता है।

एनीलिंग पाश

मैं एक पूर्ण प्रदर्शनी यहां नहीं देंगे, लेकिन यह विचार सरल है। आप अपने परिचालनों का उपयोग करके मैट्रिक्स पर यादृच्छिक परिवर्तन करते हैं। ऑपरेशन के बाद मैट्रिक्स कितना "बेहतर" है (ऑपरेशन से पहले और बाद में प्रदर्शन फ़ंक्शन का उपयोग करके) मापते हैं। फिर आप तय करते हैं कि उस परिवर्तन को प्रतिबद्ध करना है या नहीं। आप इस प्रक्रिया को बहुत दोहराते हैं।

यह तय करना कि ट्रांसफॉर्म करना है या नहीं, यह तय करना है कि आपको उस ऑपरेशन को निष्पादित करना है या नहीं। एनीलिंग प्रक्रिया के अंत में, आप केवल उन परिवर्तनों को स्वीकार करते हैं जो मैट्रिक्स के स्कोर में सुधार करते हैं। लेकिन पहले, एक और अराजक समय में, आप उन परिवर्तनों की अनुमति देते हैं जो स्कोर में सुधार नहीं करते हैं। शुरुआत में, एल्गोरिदम "गर्म" होता है और कुछ भी जाता है। आखिरकार, एल्गोरिदम ठंडा होता है और केवल अच्छे परिवर्तन की अनुमति है। आप रैखिक एल्गोरिथ्म शांत है, तो एक परिवर्तन स्वीकार किया जाए या की पसंद है:

public bool ShouldAccept(double cost, double temperature, Random random) { 
    return Math.Exp(-cost/temperature) > random.NextDouble(); 
} 

आप इस एल्गोरिथ्म बारे में अधिक जानकारी के लिए Numerical Recipes में निहित उत्कृष्ट जानकारी पढ़ना चाहिए।

लंबी कहानी लघु, आपको इनमें से कुछ सामान्य उद्देश्य एल्गोरिदम सीखना चाहिए। ऐसा करने से आप विश्लेषणात्मक रूप से हल करने के लिए कठिन समस्याओं की बड़ी कक्षाओं को हल करने की अनुमति देंगे।

स्कोरिंग एल्गोरिथ्म

यह शायद trickiest हिस्सा है। आप एक ऐसे स्कोरर को तैयार करना चाहते हैं जो आपके लक्ष्य की ओर एनीलिंग प्रक्रिया का मार्गदर्शन करे। स्कोरर एक सतत कार्य होना चाहिए जिसके परिणामस्वरूप बड़ी संख्या में मैट्रिक्स आदर्श समाधान तक पहुंच जाए।

आप "आदर्श समाधान" - त्रिकोणता को कैसे मापते हैं? यहां एक बेवकूफ और आसान स्कोरर है: हर बिंदु के लिए, आप जानते हैं कि यह 1 या 0 होना चाहिए।यदि मैट्रिक्स सही है, तो स्कोर में +1 जोड़ें, -1 यदि यह गलत है। यहाँ कुछ कोड तो मैं स्पष्ट हो सकता है (परीक्षण नहीं! की समीक्षा करें!)

int Score(Matrix m) { 
    var score = 0; 
    for (var r = 0; r < m.NumRows; r++) { 
     for (var c = 0; c < m.NumCols; c++) { 
      var val = m.At(r, c); 
      var shouldBe = (c >= r) ? 1 : 0; 
      if (val == shouldBe) { 
       score++; 
      } 
      else { 
       score--; 
      } 
     } 
    } 
    return score; 
} 

इस संबंधी कलन विधि, 1s और 0 के एक यादृच्छिक क्षेत्र के साथ

0. एक के स्कोर दे देंगे "विपरीत" त्रिकोण दे देंगे सबसे नकारात्मक स्कोर, और सही समाधान सबसे सकारात्मक स्कोर देगा। दो स्कोर अलग करने से आपको लागत मिल जाएगी।

इस गणक आप के लिए काम नहीं करता है, तो आप की आवश्यकता होगी करने के लिए "धुन" यह जब तक यह मैट्रिक्स आप चाहते हैं पैदा करता है।

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

Answer 2

यहाँ एक प्रारंभिक बिंदु है।

फिर प्रत्येक पंक्ति को बाइनरी में परिवर्तित करें।

Answer 3

बेसिक एल्गोरिथ्म:

1. पंक्ति रकम का निर्धारण और मान संग्रहीत। कॉलम को और मूल्यों को संग्रहीत करें निर्धारित करें।
2. आरोही क्रम में पंक्ति रकम क्रमबद्ध करें। कॉलम आरोही क्रम में क्रमबद्ध करें।

उम्मीद है कि आपके पास एक ऊपरी-दाएं त्रिकोणीय क्षेत्र के करीब जितना संभव हो सके मैट्रिक्स होना चाहिए।

Answer 4

मैं नीचे एल्गोरिदम के साथ आया, और ऐसा लगता है कि यह सही तरीके से काम करता है।

चरण 1: 1 s तक अधिकांश के साथ कदम पंक्तियों और स्तंभों सबसे 1 रों अधिकार के साथ।

1. सबसे पहले पंक्तियां। पंक्तियों को उनके 1 एस की गणना करके क्रमबद्ध करें। हमें परवाह नहीं है यदि 2 पंक्तियों में 1 एस की समान संख्या है।
2. अब कॉलम। उनके 1 रों गिनती द्वारा कॉलम क्रमबद्ध करें। हम परवाह नहीं है अगर 2 कॉलम 1 रों का एक ही नंबर है।

चरण 2: दोहराने चरण 1 लेकिन अतिरिक्त criterions के साथ, ताकि हम त्रिकोणीय मैट्रिक्स रूप संतुष्ट।
पंक्तियों के लिए मानदंड: यदि 2 पंक्तियों में 1 एस की समान संख्या है, तो हम कोएस से शुरू होने वाली पंक्ति को स्थानांतरित करते हैं। कॉलम के लिए

मानदंड: अगर 2 कॉलम 1 एस के एक ही नंबर है, तो हम सही col तल पर है कि कम 0 रों चलते हैं।

---

उदाहरण:

चरण 1

1 2 3 4      1 2 3 4     4 1 3 2 
A 0 1 1 0     B 1 1 1 0     B 0 1 1 1 
B 1 1 1 0 - sort rows-> A 0 1 1 0 - sort cols-> A 0 0 1 1 
C 0 1 0 0     D 1 1 0 0     D 0 1 0 1 
D 1 1 0 0     C 0 1 0 0     C 0 0 0 1 

चरण 2

4 1 3 2      4 1 3 2 
B 0 1 1 1     B 0 1 1 1 
A 0 0 1 1 - sort rows-> D 0 1 0 1 - sort cols-> "completed" 
D 0 1 0 1     A 0 0 1 1 
C 0 0 0 1     C 0 0 0 1 

संपादित करें: यह पता चला है कि मेरे एल्गोरिथ्म उचित त्रिकोणीय मैट्रिक्स हमेशा नहीं देता है।
उदाहरण के लिए:

चरण 1

1 2 3 4     1 2 3 4     
A 1 0 0 0     B 0 1 1 1     
B 0 1 1 1 - sort rows-> C 0 0 1 1 - sort cols-> "completed" 
C 0 0 1 1     A 1 0 0 0     
D 0 0 0 1     D 0 0 0 1     

चरण 2

1 2 3 4     1 2 3 4     2 1 3 4 
B 0 1 1 1     B 0 1 1 1     B 1 0 1 1 
C 0 0 1 1 - sort rows-> C 0 0 1 1 - sort cols-> C 0 0 1 1 
A 1 0 0 0     A 1 0 0 0     A 0 1 0 0 
D 0 0 0 1     D 0 0 0 1     D 0 0 0 1 
          (no change) 

(*) शायद एक चरण 3अच्छा परिणाम में वृद्धि होगी। उस चरण में हम पंक्तियों को स्थान देते हैं जो शीर्ष 0 एस के साथ शुरू होते हैं।

Answer 5

द्विआधारी संख्या के रूप में व्यवहार पंक्तियाँ, सबसे महत्वपूर्ण बिट के रूप में सबसे बाईं ओर के स्तंभ के साथ, और नीचे

करने के लिए, शीर्ष अवरोही क्रम में उन्हें सॉर्ट सबसे महत्वपूर्ण बिट के रूप में सब से नीचा पंक्ति के साथ द्विआधारी संख्या के रूप में कॉलम इलाज और उन्हें आरोही क्रम में, बाएं से दाएं क्रमबद्ध करें।

जब तक आप एक निश्चित बिंदु तक नहीं पहुंच जाते तब तक दोहराएं। सबूत है कि एल्गोरिदम पाठक के लिए एक व्यायाम के रूप में छोड़ दिया जाता है।

Answer 6

अन्ना लुबिव द्वारा 1 9 87 के पेपर को "मैट्रिसेस के डबली लेक्सिकल ऑर्डरिंग" पर देखें।

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

http://dl.acm.org/citation.cfm?id=33385