algorithm
मैट्रिक्स एक्सप्लोरेशन

उदाहरण समस्याओं को हल करने के लिए मैट्रिक्स एक्सपेंशन

F (n): n ^th फाइबोनैचि संख्या ज्ञात करें। समस्या काफी आसान है जब n अपेक्षाकृत छोटा है। हम सरल पुनरावृत्ति, f(n) = f(n-1) + f(n-2) उपयोग कर सकते हैं, या हम बार-बार एक ही फ़ंक्शन की गणना से बचने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग कर सकते हैं। अगर समस्या 0 0 <n <10 find, f (n) mod 999983 मिल जाए तो आप क्या करेंगे ? डायनेमिक प्रोग्रामिंग विफल हो जाएगी, तो हम इस समस्या से कैसे निपटेंगे?

पहले देखते हैं कि मैट्रिक्स प्रतिक्षेपक पुनरावर्ती संबंध का प्रतिनिधित्व करने में कैसे मदद कर सकता है।

आवश्यक शर्तें:

• दो मैट्रिसेस को देखते हुए, अपने उत्पाद को खोजने का तरीका जानें। इसके अलावा, दो मैट्रिक्स के उत्पाद मैट्रिक्स, और उनमें से एक को देखते हुए, अन्य मैट्रिक्स को खोजने का तरीका जानें।
• आकार d x d के एक मैट्रिक्स को देखते हुए, पता है कि O (d ³ log (n)) में इसकी n ^वीं शक्ति कैसे प्राप्त करें।

पैटर्न:

पहले हमें एक पुनरावर्ती संबंध की आवश्यकता है और हम एक मैट्रिक्स एम खोजना चाहते हैं जो हमें पहले से ज्ञात राज्यों के एक सेट से वांछित स्थिति में ले जा सकता है। मान लेते हैं कि, हम किसी दिए गए पुनरावृत्ति संबंध के k राज्यों को जानते हैं और हम (k + 1) ^वें राज्य को खोजना चाहते हैं। एम होना एक कश्मीर एक्स कश्मीर मैट्रिक्स करते हैं, और हम एक मैट्रिक्स एक का निर्माण: [k एक्स 1] आवर्तन संबंध के ज्ञात राज्यों से, अब हम एक मैट्रिक्स बी प्राप्त करना चाहते हैं: [k एक्स 1] जिनमें से सेट का प्रतिनिधित्व करेंगी अगले राज्यों अर्थात एमएक्सए = बी को नीचे दिखाया गया है:

       |  f(n)  |     | f(n+1) |
       | f(n-1) |     |  f(n)  |
   M X | f(n-2) |  =  | f(n-1) |
       | ...... |     | ...... |
       | f(n-k) |     |f(n-k+1)|

तो, अगर हम एम तदनुसार डिजाइन कर सकते हैं, तो हमारा काम हो जाएगा! मैट्रिक्स का उपयोग पुनरावृत्ति संबंध का प्रतिनिधित्व करने के लिए किया जाएगा।

श्रेणी 1:
आइए सबसे सरल एक से शुरू करें, f(n) = f(n-1) + f(n-2)
हम प्राप्त करते हैं, f(n+1) = f(n) + f(n-1) ।
चलो मान लेते हैं, हम जानते हैं f(n) और f(n-1) ; हम f(n+1) का पता लगाना चाहते हैं।
ऊपर बताई गई स्थिति से, मैट्रिक्स ए और मैट्रिक्स बी को नीचे दिखाए अनुसार बनाया जा सकता है:

 Matrix A          Matrix B

|  f(n)  |        | f(n+1) |
| f(n-1) |        |  f(n)  |

[नोट: मैट्रिक्स ए को हमेशा इस तरह से डिज़ाइन किया जाएगा कि, हर राज्य जिस पर f(n+1) निर्भर करता है, प्रस्तुत किया जाएगा]
अब, हमें एक 2X2 मैट्रिक्स एम डिजाइन करने की आवश्यकता है जैसे कि, यह एमएक्सए = बी को संतुष्ट करता है जैसा कि ऊपर कहा गया है।
B का पहला तत्व f(n+1) जो वास्तव में f(n) + f(n-1) । मैट्रिक्स ए से इसे प्राप्त करने के लिए, हमें 1 एक्स एफ (एन) और 1 एक्स एफ (एन -1) की आवश्यकता है । तो एम की पहली पंक्ति [1 1] होगी ।

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| ----- |     | f(n-1) |     | ------ |

[नोट: ----- का मतलब है कि हम इस मूल्य के बारे में चिंतित नहीं हैं।]
इसी तरह, बी का दूसरा आइटम f(n) जो ए से केवल 1 एक्स एफ (एन) ले कर प्राप्त किया जा सकता है, इसलिए एम की 2 वीं पंक्ति [1 0] है।

| ----- |  X  |  f(n)  |  =  | ------ |
| 1   0 |     | f(n-1) |     |  f(n)  |

तब हम अपने वांछित 2 एक्स 2 मैट्रिक्स एम प्राप्त करते हैं ।

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

ये मेट्रिक्स केवल मैट्रिक्स गुणा का उपयोग करके निकाले जाते हैं।

टाइप 2:

चलो इसे थोड़ा जटिल बनाते हैं: f(n) = a X f(n-1) + b X f(n-2) , जहां ए और बी स्थिरांक हैं।
यह हमें बताता है, f(n+1) = a X f(n) + b X f(n-1) ।
अब तक, यह स्पष्ट होना चाहिए कि मेट्रिसेस का आयाम निर्भरता की संख्या के बराबर होगा, अर्थात इस विशेष उदाहरण में, फिर से 2. इसलिए ए और बी के लिए , हम आकार 2 एक्स 1 के दो मैट्रीक का निर्माण कर सकते हैं:

Matrix A             Matrix B
|  f(n)  |          | f(n+1) |
| f(n-1) |          |  f(n)  |

अब f(n+1) = a X f(n) + b X f(n-1) , हमें उद्देश्य मैट्रिक्स M की पहली पंक्ति में [a, b] की आवश्यकता है। और बी में 2 आइटम के लिए, यानी f(n) हम पहले से ही मैट्रिक्स ए में है , इसलिए हम सिर्फ वही लेते हैं, जो मैट्रिक्स एम की दूसरी पंक्ति को [1 0] पर ले जाता है। इस बार हमें मिलेगा:

| a   b |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

बहुत सरल, एह?

टाइप 3:

यदि आप इस चरण से बच गए हैं, तो आप बहुत बड़े हो गए हैं, अब थोड़ा जटिल संबंध का सामना करते हैं: f(n) = a X f(n-1) + c X f(n-3) खोजें?
ओह! कुछ मिनट पहले, हमने देखा कि सभी सन्निहित राज्य थे, लेकिन यहाँ, राज्य f (n-2) गायब है। अभी?

वास्तव में यह कोई समस्या नहीं है, हम संबंध को इस प्रकार परिवर्तित कर सकते हैं: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) घटाते हुए f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) । अब, हम देखते हैं कि, यह वास्तव में टाइप 2 में वर्णित एक फॉर्म है। इसलिए यहां ऑब्जेक्टिव मैट्रिक्स एम 3 एक्स 3 होगा , और एलिमेंट्स:

| a 0 c |     |  f(n)  |     | f(n+1) |
| 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
| 0 1 0 |     | f(n-2) |     | f(n-1) |

इनकी गणना उसी प्रकार से की जाती है जैसे टाइप 2, यदि आपको यह कठिन लगता है, तो इसे पेन और पेपर पर आज़माएँ।

टाइप 4:

जीवन नरक के रूप में जटिल हो रहा है, और श्री, समस्या अब आपसे f(n) = f(n-1) + f(n-2) + c को खोजने के लिए कहती है जहाँ c कोई स्थिर है।
अब यह एक नया है और हम सब अतीत में देख चुके हैं, गुणा के बाद, ए में प्रत्येक राज्य बी में अपने अगले राज्य में बदल जाता है।

f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
.................... so on

इसलिए, आम तौर पर हम इसे पिछले फैशन के माध्यम से प्राप्त नहीं कर सकते हैं, लेकिन कैसे हम एक राज्य के रूप में सी जोड़ते हैं:

      |  f(n)  |   | f(n+1) |
  M X | f(n-1) | = |  f(n)  |
      |    c   |   |    c   |

अब, एम को डिजाइन करने के लिए इसकी बहुत मुश्किल नहीं है। यहां बताया गया है कि यह कैसे किया जाता है, लेकिन सत्यापित करना न भूलें:

  | 1 1 1 |     |  f(n)  |     | f(n+1) |
  | 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
  | 0 0 1 |     |    c   |     |    c   |

टाइप 5:

आइए इसे पूरी तरह से लगाएं: f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e । आइए इसे आपके लिए एक अभ्यास के रूप में छोड़ दें। पहले राज्यों और मैट्रिक्स एम का पता लगाने की कोशिश करें। और जांचें कि क्या यह आपके समाधान के साथ मेल खाता है। मैट्रिक्स ए और बी भी खोजें।

| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |

टाइप 6:

कभी-कभी पुनरावृत्ति इस तरह दी जाती है:

f(n) = f(n-1)   -> if n is odd
f(n) = f(n-2)   -> if n is even

संक्षेप में:

f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)

यहां, हम फ़ंक्शन को विषम के आधार पर भी विभाजित कर सकते हैं और उन दोनों के लिए 2 अलग-अलग मैट्रिक्स रख सकते हैं और उन्हें अलग से गणना कर सकते हैं।

टाइप 7:

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

g(n) = 2g(n-1) + 2g(n-2) + f(n)

यहाँ, पुनरावर्तन g (n) f(n) पर निर्भर है और इसकी गणना एक ही मैट्रिक्स में की जा सकती है लेकिन बढ़े हुए आयामों की। इनमें से चलो पहली बार में मेट्रिसेस A और B को डिज़ाइन करते हैं।

 Matrix A            Matrix B
|  g(n)  |          | g(n+1) |
| g(n-1) |          |  g(n)  |
| f(n+1) |          | f(n+2) |
|  f(n)  |          | f(n+1) |

यहाँ, g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) । अब, ऊपर बताई गई प्रक्रियाओं का उपयोग करके, हम उद्देश्य मैट्रिक्स M को पा सकते हैं:

| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |

तो, ये पुनरावृत्ति संबंधों की मूल श्रेणियां हैं जो इस सरल तकनीक को हल करने के लिए उपयोग की जाती हैं।