आव्यूह श्रृंखला गुणन

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

इसके कई विकल्प हैं क्योंकि आव्यूह गुणन साहचर्य है। दूसरे शब्दों में, कोई प्रभाव नहीं पड़ता की गुणनफल किस प्रकार से कोष्ठक में प्रस्तुत किया गया है, प्राप्त परिणाम वही रहता है। उदाहरण के लिए, चार मैट्रिक्स A,B, C और D के लिए, पांच संभावित विकल्प हैं:

((AB)C)D = (A(BC))D = (AB) (CD) = A((BC)D) = A(B(CD))।

यद्यपि यह उत्पाद को प्रभावित नहीं करता है, जिस क्रम में शब्दों को कोष्ठक में रखा गया है, वह उत्पाद की गणना करने के लिए आवश्यक सरल अंकगणितीय क्रियाओं की संख्या अर्थात कम्प्यूटेशनल जटिलता को प्रभावित करता है। आव्यूह X × Y का आव्यूह Y × Z द्वारा गुणन करने के लिए XYZ साधारण गुणन और X(Y − 1)Z साधारण जोड़ की आवश्यक्ता होती है। इस संदर्भ में, क्रियाशील जटिलता के माप के रूप में साधारण गुणन की संख्या का उपयोग करना विशिष्ट है।

यदि A एक 10 × 30 आव्यूह है, B एक 30 × 5 आव्यूह है, और C एक 5 × 60 आव्यूह है, तो

कंप्यूटिंग (ab)c की (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 संचालन की आवश्यक्ता है, यद्यपि की

कंप्यूटिंग a(bc) की (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 संचालन की आवश्यक्ता है ।

स्पष्ट रूप से पहली विधि अधिक कुशल है। इस सुचना के साथ, समस्या कथन को परिष्कृत किया जा सकता है कि n आव्यूहों के उत्पाद का इष्टतम कोष्ठक कैसे निर्धारित किया जाए? प्रत्येक संभावित कोष्ठक (पाशविक बल) की जाँच करने के लिए क्रियाशील समय की जटिलता की आवश्यकता होगी | समस्या को संबंधित उप-समस्याओं के समूह में तोड़कर इस समस्या का त्वरित समाधान प्राप्त किया जा सकता है।

एक गतिशील अंकगणितीय प्रोग्रामिंग

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

• आव्यूहों का क्रम लें और इसे दो क्रमों में अलग करें।
• प्रत्येक अनुवर्ती को गुणा करने की न्यूनतम लागत ज्ञात कीजिए।
• इन लागतों को एक साथ जोड़ें, और दो परिणाम आव्यूह को गुणा करने की लागत में जोड़ें।
• यह प्रत्येक संभावित स्थिति के लिए करें जिस पर आव्यूह के अनुक्रम को विभाजित किया जा सकता है, और उन सभी पर न्यूनतम मान प्रत्यारोपित करते है ।

उदाहरण के लिए, यदि हमारे पास चार मैट्रिक्स एबीसीडी हैं, तो हम (A) (BCD), (AB) (CD), और (ABC) (D) में से प्रत्येक को प्राप्त के लिए आवश्यक लागत की गणना करते हैं, न्यूनतम लागत प्राप्त करने के लिए पुनरावर्ती करते हैं। ABC,AB, CD और BCD की गणना करते है। इसके पश्चात हम सबसे अच्छे वाले को चुनते है। अभी भी, यह न केवल न्यूनतम लागत प्रदान करता है, अपितु गुणा करने का सबसे अच्छा युक्ति भी प्रदर्शित करता है: इसे उस युक्ति से समूहित करते है जो सबसे कम कुल लागत प्रदान करता है, तथा प्रत्येक कारक के लिए ऐसा ही किया जाता है।

चुकी, इस एल्गोरिथ्म में घातीय क्रियाशील जटिलता है जो इसे सभी क्रमपरिवर्तनों को जांचने के दृष्टिकोण के रूप में अक्षम बनाती है। इसका कारण एल्गोरिदम का बहुत अधिक अनावश्यक कार्य करना है। उदाहरण के लिए, ऊपर हमने ABC और AB दोनों की गणना के लिए सर्वोत्तम लागत खोजने के लिए एक पुनरावर्ती की थी। परन्तु ABC की गणना के लिए सर्वोत्तम लागत खोजने के लिए AB के लिए भीं सर्वोत्तम लागत खोजने की आवश्यकता है। जैसे-जैसे पुनरावर्तन बढ़ता जाता है, इस प्रकार की अनावश्यक पुनरावृत्ति अधिक से अधिक होती जाती है।

एक सरल समाधान को memoization कहा जाता है: हर बार जब हम एक विशिष्ट परिणाम को गुणा करने के लिए आवश्यक न्यूनतम लागत की गणना करते हैं, तो हम इसे बचा लेते हैं। यदि हमें कभी भी इसकी गणना करने के लिए कहा जाता है, तो हम केवल सहेजा गया उत्तर देते हैं, और इसकी पुनर्गणना नहीं करते हैं। चूंकि लगभग एन हैं²/2 अलग-अलग अनुवर्ती, जहां n आव्यूहों की संख्या है, ऐसा करने के लिए आवश्यक स्थान उचित है। यह दिखाया जा सकता है कि यह सरल ट्रिक रनटाइम को O(n³) O से (2ⁿ), जो वास्तविक अनुप्रयोगों के लिए पर्याप्त से अधिक कुशल है। यह टॉप-डाउन और बॉटम-अप डिज़ाइन | टॉप-डाउन डायनामिक प्रोग्रामिंग है।

निम्नलिखित नीचे-ऊपर दृष्टिकोण गणना करता है, प्रत्येक 2 ≤ k ≤ n के लिए, पहले से गणना की गई छोटी अनुगामी की लागत का उपयोग करके लंबाई k के सभी अनुवर्ती की न्यूनतम लागत। इसमें समान स्पर्शोन्मुख रनटाइम है और इसके लिए किसी पुनरावर्तन की आवश्यकता नहीं है।

स्यूडोकोड:

// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
MatrixChainOrder(int dims[])
{
    // length[dims] = n + 1
    n = dims.length - 1;
    // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
    // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
    // The cost is zero when multiplying one matrix
    for (i = 1; i <= n; i++)
        m[i, i] = 0;

    for (len = 2; len <= n; len++) { // Subsequence lengths
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
            m[i, j] = MAXINT;
            for (k = i; k <= j - 1; k++) {
                cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
                if (cost < m[i, j]) {
                    m[i, j] = cost;
                    s[i, j] = k; // Index of the subsequence split that achieved minimal cost
                }
            }
        }
    }
}

• ध्यान दें: dims के लिए पहला इंडेक्स 0 है और m और s के लिए पहला इंडेक्स 1 है।

मानक पुस्तकालय से मेमोइज़ेशन डेकोरेटर का उपयोग करके एक पायथन (प्रोग्रामिंग भाषा) कार्यान्वयन:

<वाक्यविन्यास लैंग = पायथन 3> functools आयात कैश से

डीफ़ मैट्रिक्स चेनऑर्डर (मंद: सूची [int]) -> int:

   @cache
   डेफ ए (i, जे):
       रिटर्न मिन ((ए (आई, के) + मंद [i] * मंद [के] * मंद [जे] + ए (के, जे)
                  के लिए सीमा में (i + 1, j)), डिफ़ॉल्ट = 0)

   रिटर्न ए (0, लेन (मंद) - 1)

</वाक्यविन्यास हाइलाइट>

संचालन के हल किए गए क्रम को प्रिंट करने के लिए एक सुविधा विधि के साथ-साथ शून्य-आधारित सरणी अनुक्रमणिका का उपयोग करते हुए एक जावा (प्रोग्रामिंग भाषा) कार्यान्वयन:

सिंटैक्सहाइलाइट लैंग = जावा> पब्लिक क्लास मैट्रिक्सऑर्डरऑप्टिमाइजेशन {

   संरक्षित int[][]m;
   संरक्षित int[][]s;

   सार्वजनिक शून्य मैट्रिक्स चेनऑर्डर (इंट [] मंद) {
       int n = dims.length - 1;
       एम = नया इंट [एन] [एन];
       एस = नया इंट [एन] [एन];

       for (int lenMinusOne = 1; lenMinusOne <n; lenMinusOne++) {
           for (int i = 0; i <n - lenMinusOne; i++) {
               int j = i + lenMinusOne;
               m[i][j] = Integer.MAX_VALUE;
               के लिए (int k = i; k <j; k++) {
                   int लागत = m[i][k] + m[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
                   अगर (लागत <एम [i] [जे]) {
                       एम [मैं] [जे] = लागत;
                       एस [मैं] [जे] = के;
                   }
               }
           }
       }
   }

   सार्वजनिक शून्य प्रिंटऑप्टिमल पेरेंटिसाइजेशन () {
       बूलियन [] inAResult = नया बूलियन [s.length];
       PrintOptimalParenthesizations(s, 0, s.length - 1, inAResult);
   }

   void printOptimalParenthesizations(int[][]s, int i, int j, /* सुंदर प्रिंटिंग के लिए: */ बूलियन[] inAResult) {
       अगर (मैं! = जे) {
           PrintOptimalParenthesizations(s, i, s[i][j], inAResult);
           PrintOptimalParenthesizations(s, s[i][j] + 1, j, inAResult);
           स्ट्रिंग istr = inAResult [i]? _परिणाम   :    ;
           स्ट्रिंग jstr = inAResult [जे]? _परिणाम   :    ;
           System.out.println (ए_ + आई + आईएसटीआर + * ए_ + जे + जेएसटी);
           परिणाम में [i] = सत्य;
           परिणाम में [जे] = सच;
       }
   }

} </वाक्यविन्यास हाइलाइट>

इस कार्यक्रम के अंत में, हमारे पास पूर्ण अनुक्रम के लिए न्यूनतम लागत है।

अधिक कुशल एल्गोरिदम

ऐसे एल्गोरिदम हैं जो O(n³) डायनेमिक प्रोग्रामिंग एल्गोरिदम, हालांकि वे अधिक जटिल हैं।

हू और शिंग

हू और शिंग द्वारा प्रकाशित एल्गोरिद्म O(n log n) कम्प्यूटेशनल जटिलता प्राप्त करता है। उन्होंने दिखाया कि कैसे मैट्रिक्स श्रृंखला गुणा समस्या को एक नियमित बहुभुज के बहुभुज त्रिभुज की समस्या में परिवर्तित (या कमी (जटिलता)) किया जा सकता है। बहुभुज इस तरह उन्मुख होता है कि एक क्षैतिज निचला भाग होता है, जिसे आधार कहा जाता है, जो अंतिम परिणाम का प्रतिनिधित्व करता है। बहुभुज की अन्य n भुजाएँ, दक्षिणावर्त दिशा में, आव्यूहों का प्रतिनिधित्व करती हैं। एक पक्ष के प्रत्येक छोर पर शीर्ष उस पक्ष द्वारा दर्शाए गए मैट्रिक्स के आयाम हैं। गुणन श्रृंखला में n मेट्रिसेस के साथ n−1 बाइनरी ऑपरेशन और C हैं_n−1 कोष्ठक लगाने के तरीके, जहाँ C_n−1 (n−1)-वीं कैटलन संख्या है। एल्गोरिदम शोषण करता है कि सी भी हैं_n−1 n+1 भुजाओं वाले बहुभुज के संभावित त्रिभुज।

यह छवि एक नियमित षट्भुज के संभावित त्रिभुजों को दर्शाती है। ये अलग-अलग तरीकों से मेल खाते हैं जो 5 मैट्रिसेस के उत्पाद के लिए गुणा करने के लिए कोष्ठकों को रखा जा सकता है।

नीचे दिए गए उदाहरण के लिए, चार भुजाएँ हैं: A, B, C और अंतिम परिणाम ABC। A एक 10×30 मैट्रिक्स है, B एक 30×5 मैट्रिक्स है, C एक 5×60 मैट्रिक्स है, और अंतिम परिणाम 10×60 मैट्रिक्स है। इस उदाहरण के लिए नियमित बहुभुज एक 4-गॉन है, अर्थात एक वर्ग:

मैट्रिक्स उत्पाद AB एक 10x5 मैट्रिक्स है और BC एक 30x60 मैट्रिक्स है। इस उदाहरण में दो संभावित त्रिभुज हैं:

• 

  (AB)C का बहुभुज प्रतिनिधित्व

• 

  A(BC) का बहुभुज प्रतिनिधित्व

आवश्यक गुणन की संख्या के संदर्भ में एकल त्रिभुज की लागत उसके शीर्षों का गुणनफल है। बहुभुज के एक विशेष त्रिभुज की कुल लागत उसके सभी त्रिभुजों की लागतों का योग है:

(AB)C: (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 गुणन

A(BC): (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 गुणन

हू एंड शिंग ने एक एल्गोरिद्म विकसित किया जो O(n log n) समय में न्यूनतम लागत विभाजन समस्या के लिए एक इष्टतम समाधान ढूंढता है। एल्गोरिथम की शुद्धता का उनका प्रमाण लेम्मा 1 पर निर्भर करता है जो 1981 की तकनीकी रिपोर्ट में साबित हुआ और प्रकाशित पेपर से हटा दिया गया।लेम्मा की तकनीकी रिपोर्ट का प्रमाण गलत है, लेकिन शिंग ने एक सही प्रमाण प्रस्तुत किया है।

अन्य ओ (एन लॉग एन) एल्गोरिदम

वांग, झू और तियान ने एक सरलीकृत O(n log m) एल्गोरिथम प्रकाशित किया है, जहां n श्रृंखला में मैट्रिक्स की संख्या है और m दी गई मैट्रिक्स श्रृंखला के आयाम अनुक्रम में स्थानीय न्यूनतम की संख्या है। निम्बार्क, गोहेल और दोशी ने एक लालची ओ(एन लॉग एन) एल्गोरिथम प्रकाशित किया है, लेकिन उनकी इष्टतमता का प्रमाण गलत है और उनका एल्गोरिथ्म कुछ मैट्रिक्स श्रृंखलाओं के लिए सबसे कुशल कोष्ठक असाइनमेंट का उत्पादन करने में विफल रहता है।

चिन-हू-शिंग अनुमानित समाधान

चिन द्वारा स्वतंत्र रूप से बनाया गया एल्गोरिथम और हू एंड शिंग ओ (एन) में चलता है और एक कोष्ठक उत्पन्न करता है जो इष्टतम विकल्प से अधिकतम 15.47% खराब है। ज्यादातर मामलों में एल्गोरिदम इष्टतम समाधान या समाधान उत्पन्न करता है जो इष्टतम से केवल 1-2 प्रतिशत खराब होता है।

एल्गोरिथ्म समस्या को बहुभुज विभाजन समस्या में अनुवाद करके शुरू होता है। बहुभुज के प्रत्येक शीर्ष V से एक भार w जुड़ा होता है। मान लीजिए कि हमारे पास लगातार तीन शीर्ष हैं $V_{i-1},V_{i},V_{i+1}$, ओर वो $V_{\min }$ न्यूनतम वजन वाला शीर्ष है $w_{\min }$. हम चतुर्भुज को शीर्षों के साथ देखते हैं $V_{\min },V_{i-1},V_{i},V_{i+1}$ (दक्षिणावर्त क्रम में)। हम इसे दो तरह से त्रिभुज कर सकते हैं:

• $(V_{\min },V_{i-1},V_{i})$ और $(V_{\min },V_{i+1},V_{i})$, लागत के साथ $w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}$
• $(V_{\min },V_{i-1},V_{i+1})$ और $(V_{i-1},V_{i},V_{i+1})$ लागत के साथ $w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}$.

इसलिए, अगर

$w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}$

या समकक्ष

${\frac {1}{w_{i}}}+{\frac {1}{w_{\min }}}<{\frac {1}{w_{i+1}}}+{\frac {1}{w_{i-1}}}$

हम शीर्ष को हटा देते हैं $V_{i}$ बहुभुज से और भुजा जोड़ें $(V_{i-1},V_{i+1})$ त्रिकोण को। हम इस प्रक्रिया को तब तक दोहराते हैं जब तक कि नहीं $V_{i}$ ऊपर की स्थिति को संतुष्ट करता है। शेष सभी शीर्षों के लिए $V_{n}$, हम पक्ष जोड़ते हैं $(V_{\min },V_{n})$ त्रिकोण को। यह हमें लगभग इष्टतम त्रिभुज देता है।

सामान्यीकरण

मैट्रिक्स श्रृंखला गुणन समस्या एक अधिक सार समस्या को हल करने के लिए सामान्यीकृत करती है: वस्तुओं का एक रैखिक अनुक्रम दिया जाता है, उन वस्तुओं पर एक साहचर्य बाइनरी ऑपरेशन, और किसी भी दो वस्तुओं पर उस ऑपरेशन को करने की लागत की गणना करने का एक तरीका (साथ ही सभी आंशिक) परिणाम), अनुक्रम पर ऑपरेशन को लागू करने के लिए वस्तुओं को समूहित करने के लिए न्यूनतम लागत तरीके की गणना करें। इसका कुछ हद तक काल्पनिक विशेष मामला स्ट्रिंग्स की सूची का स्ट्रिंग संयोजन है। सी (प्रोग्रामिंग भाषा) में, उदाहरण के लिए, स्ट्रैट का उपयोग करके लंबाई एम और एन के दो तारों को जोड़ने की लागत ओ (एम + एन) है, क्योंकि हमें पहली स्ट्रिंग के अंत को खोजने के लिए ओ (एम) समय की आवश्यकता है और ओ ( एन) दूसरी स्ट्रिंग को इसके अंत में कॉपी करने का समय। इस लागत फ़ंक्शन का उपयोग करके, हम स्ट्रिंग्स के अनुक्रम को जोड़ने का सबसे तेज़ तरीका खोजने के लिए एक गतिशील प्रोग्रामिंग एल्गोरिदम लिख सकते हैं। हालाँकि, यह अनुकूलन बेकार है क्योंकि हम सीधे समय में स्ट्रिंग्स को उनकी लंबाई के योग के अनुपात में जोड़ सकते हैं। एकल लिंक्ड सूचियों के लिए एक समान समस्या मौजूद है।

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

यह भी देखें

• असोसिएहेड्रोन
• तामरी जाली