बूलियन मैट्रिक्स गुणा एल्गोरिदम

Question

यह स्टैक ओवरफ्लो पर मेरा पहला प्रश्न है। मैं गुड्रिच, तामासिया द्वारा "एल्गोरिदम डिजाइन" से कुछ अभ्यासों को हल कर रहा हूं। हालांकि, मैं इस समस्या के बारे में काफी अनजान हूं। Unusre कहां से शुरू करना है और कैसे आगे बढ़ना है। कोई भी सलाह बहुत उपयोगी होगी। यहां समस्या है:

बूलियन मैट्रिस मैट्रिस हैं जैसे प्रत्येक प्रविष्टि 0 या 1 है, और मैट्रिक्स गुणा का उपयोग * और OR के लिए + के द्वारा किया जाता है। मान लीजिए कि हमें दो एनएक्सएन यादृच्छिक बूलियन मैट्रिस ए और बी दिए गए हैं, ताकि संभावना है कि कोई प्रविष्टि या तो 1 है, 1/k है। दिखाएं कि यदि के स्थिर है, तो ए और बी गुणा करने के लिए एक एल्गोरिदम है जिसका अपेक्षित चलने का समय ओ (एन^2) है। क्या होगा अगर के एन है?

Answer 1

मैट्रिक्स मानक पुनरावृत्ति दृष्टिकोण का उपयोग कर गुणन हे है (एन), तुम पर एन पंक्तियों और एन कॉलम पुनरावृति करना होगा, और प्रत्येक तत्व के लिए पंक्तियों में से एक और स्तंभों में से एक का एक वेक्टर गुणा करते हैं, क्योंकि , जो एन गुणा और एन -1 जोड़ों लेता है। समस्या के रूप में विनिर्दिष्ट

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     int sum = 0; 
     for(m = 0; m < n; m++) 
     { 
      sum += a[i][m] * b[m][j]; 
     } 
     c[i][j] = sum; 
    } 
} 

एक बूलियन मैट्रिक्स के लिए, और गुणा के जगह में और या के स्थान पर प्रयोग किया जाता है:

छद्म कोड मैट्रिक्स ग में मैट्रिक्स ख और दुकान से मैट्रिक्स एक गुणा करने के लिए इसके अलावा, तो यह हो जाता है इस:

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     boolean value = false; 
     for(m = 0; m < n; m++) 
     { 
      value ||= a[i][m] && b[m][j]; 
      if(value) 
       break; // early out 
     } 
     c[i][j] = value; 
    } 
} 

यहाँ सूचना के लिए बात यह है कि एक बार हमारे बूलियन "राशि" सच है, हम गणना और जल्दी अंतरतम लूप से बाहर बंद कर सकते हैं, क्योंकि ट्रू साथ बाद में किसी भी मूल्यों oring है ई सच साबित करने जा रहा है, इसलिए हम तुरंत जान सकते हैं कि अंतिम परिणाम सच होगा।

किसी भी स्थिर k के लिए, हम इसे जल्दी से करने से पहले संचालन की संख्या (मूल्यों को यादृच्छिक मानते हैं) के पर निर्भर होने जा रहा है और एन के साथ नहीं बढ़ेगा। प्रत्येक पुनरावृत्ति पर एक (1/के) मौका होगा कि लूप समाप्त हो जाएगा, क्योंकि इसके लिए हमें दो 1s की आवश्यकता है और प्रत्येक प्रविष्टि 1 का 1 होने का मौका है। समाप्ति से पहले पुनरावृत्तियों की संख्या Geometric distribution का पालन करेगी जहां पी है (1/के) , और "सफलता" (लूप से बाहर तोड़ने से पहले) "परीक्षण" (पुनरावृत्तियों) की अपेक्षित संख्या एन पर निर्भर नहीं है (परीक्षणों की संख्या के लिए ऊपरी बाउंड को छोड़कर) ताकि आंतरिकतम लूप एक दिए गए के लिए स्थिर समय (औसत पर) में चलता है, समग्र एल्गोरिदम ओ (एन) बनाते हैं। ज्यामितीय वितरण सूत्र आपको कुछ अंतर्दृष्टि देना चाहिए कि क्या होता है यदि k = n। ध्यान दें कि विकिपीडिया के सूत्र में दिए गए सूत्र में परीक्षणों की संख्या है।