dynamic-programming
मैट्रिक्स चेन गुणा

पुनरावर्ती समाधान

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

मान लें कि हमारे पास आयाम ₁ * n और p * q के दो मैट्रिक्स A ₁ और A ₂ हैं। मैट्रिक्स गुणा के नियमों से, हम जानते हैं कि,

1. हम ए ₁ और ए ₂ को गुणा कर सकते हैं यदि और केवल यदि एन = पी । इसका मतलब है कि A ₁ के कॉलम की संख्या A ₂ की पंक्तियों की संख्या के बराबर होनी चाहिए।
2. तो पहली शर्त संतुष्ट है और हम गुणा एक ₁ करते हैं और एक _2, हम एक नए मैट्रिक्स मिल जाएगा, चलो यह आयाम मीटर * क्ष का एक ₃ कहते हैं।
3. ए ₁ और ए ₂ को गुणा करने के लिए, हमें कुछ स्केलर गुणा करने की आवश्यकता है। स्केलर गुणन की कुल संख्या, हमें प्रदर्शन करने की आवश्यकता है ( एम * एन * क्यू ) या ( एम * पी * क्यू )।
4. A ₁ * A ₂ A ₂ * A _{1 के} बराबर नहीं है।

यदि हमारे पास क्रमशः तीन ए ₁ , ए ₂ और ए ₃ वाले आयाम एम * एन , एन * पी और पी * क्यू हैं, तो ए ₄ = ए ₁ * ए ₂ * ए ₃ में एम * क्यू का आयाम होगा। अब हम इस मैट्रिक्स गुणन को दो तरीकों से कर सकते हैं:

• पहले हम ए ₁ और ए _{2 को} गुणा करते हैं, फिर परिणाम के साथ हम ए _{3 को} गुणा करते हैं। वह है: ( ए ₁ * ए ₂ ) * ए ₃ ।
• पहले हम ए ₂ और ए _{3 को} गुणा करते हैं, फिर परिणाम के साथ हम ए _{1 को} गुणा करते हैं। वह है: ए _१ * ( ए _२ * ए _३ )।

आप देख सकते हैं कि गुणन का क्रम समान रहता है, अर्थात हम गुणा नहीं करते ( A ₁ * A ₃ ) * A ₂ क्योंकि यह मान्य नहीं हो सकता है। हम केवल शेष के साथ गुणा करने से पहले एक कोष्ठक को गुणा करने के लिए बदलते हैं। हम इन कोष्ठकों को कैसे स्थान देते हैं यह महत्वपूर्ण है। क्यों? मान लीजिए, 3 मैट्रिसेस ए ₁ , ए ₂ और ए ₃ के आयाम 10 * 100 , 100 * 5 , 5 * 50 हैं । फिर,

1. के लिए ( ए ₁ * ए ₂ ) * ए ₃ , स्केलर गुणन की कुल संख्या हैं: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 बार।
2. ए ₁ * ( ए ₂ * ए ₃ ) के लिए, स्केलर गुणन की कुल संख्या हैं: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 बार।

दूसरे प्रकार के लिए स्केलर गुणन की संख्या 1 प्रकार की संख्या से 10 गुना है! इसलिए यदि आप कुल स्केलर गुणा को कम करने के लिए आवश्यक कोष्ठक के सही अभिविन्यास का पता लगाने के लिए एक तरीका तैयार कर सकते हैं, तो यह मैट्रिक्स गुणा के लिए आवश्यक समय और मेमोरी दोनों को कम करेगा। यह वह जगह है जहां मैट्रिक्स श्रृंखला गुणन काम में आता है। यहां, हम मैट्रिस के वास्तविक गुणन से चिंतित नहीं होंगे, हम केवल सही कोष्ठक क्रम का पता लगाएंगे ताकि स्केलर गुणा की संख्या कम से कम हो। हमारे पास A ₁ , A ₂ , A ₃ ........ A _{n होगा} और हम इनको गुणा करने के लिए आवश्यक स्केलर गुणन की न्यूनतम संख्या ज्ञात करेंगे। हम मान लेंगे कि दिए गए आयाम मान्य हैं, अर्थात यह मैट्रिक्स गुणन के लिए हमारी पहली आवश्यकता को पूरा करता है।

हम इस समस्या को हल करने के लिए divide-and-conquer विधि का उपयोग करेंगे। आम सबप्रॉब्लम की वजह से डायनामिक प्रोग्रामिंग की जरूरत होती है। उदाहरण के लिए: n = 5 के लिए , हमारे पास 5 मैट्रिसेस ए ₁ , ए ₂ , ए ₃ , ए ₄ और ए _{5 हैं} । हम इस मैट्रिक्स गुणन A ₁ * A ₂ * A ₃ * A ₄ * A ₅ को करने के लिए आवश्यक गुणा की न्यूनतम संख्या का पता लगाना चाहते हैं। कई तरीकों में से, हम एक पर ध्यान केंद्रित करते हैं: ( ए ₁ * ए ₂ ) * ( ए ₃ * ए ₄ * ए ₅ )।

इस एक के लिए, हम A _बाएँ = A ₁ * A _{2 का पता लगाएंगे} । एक _{अधिकार} = एक ₃ * ए ₄ * ए ₅ । फिर हम एक _{उत्तर} = एक _{बायां} * एक _{दायां पता लगाएंगे} । Scaler एक _जवाब पता लगाने के लिए की जरूरत गुणा की कुल संख्या: = scaler गुणा की कुल संख्या निर्धारित करने के लिए एक _{छोड़ दिया} + scaler एक _सही + scaler निर्धारित करने के लिए एक _{छोड़ दिया} की जरूरत गुणा की कुल संख्या का निर्धारण करने के लिए आवश्यक गुणा की कुल संख्या की जरूरत * एक _{अधिकार} ।

पिछले अवधि, scaler एक के निर्धारण की आवश्यकता गुणा की कुल संख्या _{छोड़ दिया} * एक _सही लिखा जा सकता है के रूप में: एक में पंक्तियों की संख्या _{छोड़ दिया} * एक में स्तंभों की संख्या _{छोड़ दिया} * एक _सही में स्तंभों की संख्या। (मैट्रिक्स गुणन के दूसरे नियम के अनुसार)

लेकिन हम अन्य तरीकों से भी कोष्ठक निर्धारित कर सकते हैं। उदाहरण के लिए:

• ए ₁ * ( ए ₂ * ए ₃ * ए ₄ * ए ₅ )
• ( A ₁ * A ₂ * A ₃ ) * ( A ₄ * A ₅ )
• ( ए _१ * ए _२ * ए _३ * ए _४ ) * ए _५ आदि।

प्रत्येक और हर संभव मामलों के लिए, हम ए _बाएँ और ए _दाएं का पता लगाने के लिए आवश्यक स्केलर गुणन की संख्या निर्धारित करेंगे, फिर ए _बाएं * ए _{दाएं के लिए} । यदि आपके पास पुनरावृत्ति के बारे में एक सामान्य विचार है, तो आप पहले ही समझ चुके हैं कि इस कार्य को कैसे करना है। हमारा एल्गोरिदम होगा:

- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.

यह गतिशील प्रोग्रामिंग समस्या क्यों है? यह निर्धारित करने के लिए ( ए ₁ * ए ₂ * ए ₃ ), यदि आपने पहले ही गणना की है ( ए ₁ * ए ₂ ), तो यह इस मामले में मददगार होगा।

इस पुनरावृत्ति की स्थिति का निर्धारण करने के लिए, हम देख सकते हैं कि प्रत्येक मामले को हल करने के लिए, हमें यह जानने की आवश्यकता होगी कि मैट्रिस की सीमा आपके साथ क्या है। तो हम एक शुरुआत और अंत की आवश्यकता होगी। जैसा कि हम विभाजित और जीत का उपयोग कर रहे हैं, हमारा आधार मामला 2 से कम मेट्रिसेस ( शुरुआती > = अंत ) होगा, जहां हमें बिल्कुल भी गुणा करने की आवश्यकता नहीं है। हमारे पास 2 सरणियाँ होंगी: पंक्ति और स्तंभ । पंक्ति [i] और कॉलम [i] मैट्रिक्स ए _{i के} लिए पंक्तियों और स्तंभों की संख्या को संग्रहीत करेगा। हमारे पास पहले से गणना किए गए मानों को संग्रहीत करने और इसे -1 के साथ आरंभ करने के लिए एक dp [n] [n] सरणी होगी, जहां -1 का प्रतिनिधित्व करता है, लेकिन मूल्य की गणना अभी तक नहीं की गई है। dp [i] [j] एक _i , A _{i + 1} , ....., A _j समावेशी गुणा करने के लिए आवश्यक स्केलर गुणन की संख्या का प्रतिनिधित्व करता है। छद्म कोड की तरह दिखेगा:

Procedure matrixChain(begin, end):
if begin >= end
    Return 0
else if dp[begin][end] is not equal to -1
    Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
    operation_for_left := matrixChain(begin, mid)
    operation_for_right := matrixChain(mid+1, right)
    operation_for_left_and_right := row[begin] * column[mid] * column[end]
    total := operation_for_left + operation_for_right + operation_for_left_and_right
    answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]

जटिलता:

शुरू और अंत का मूल्य 1 से n तक हो सकता है । N ² अलग-अलग राज्य हैं। प्रत्येक राज्यों के लिए, अंदर लूप n बार चलेगा। कुल समय जटिलता: O(n³) और मेमोरी जटिलता: O(n²) । O(n²) ।