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

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

इसके कई विकल्प हैं क्योंकि आव्यूह गुणन साहचर्य है। दूसरे शब्दों में, कोई प्रभाव नहीं पड़ता की गुणनफल किस प्रकार से कोष्ठक में प्रस्तुत किया गया है, प्राप्त परिणाम वही रहता है। उदाहरण के लिए, चार मैट्रिक्स 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 आव्यूहों के उत्पाद का इष्टतम कोष्ठक कैसे निर्धारित किया जाए? प्रत्येक संभावित कोष्ठक (पाशविक बल) की जाँच करने के लिए क्रियाशील समय की जटिलता की आवश्यकता होगी | समस्या को संबंधित उप-समस्याओं के समूह में तोड़कर इस समस्या का त्वरित समाधान प्राप्त किया जा सकता है।

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

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

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

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

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

एक सरल समाधान को मेमोराइज़ेशन कहा जाता है: प्रत्येक बार जब हम एक विशिष्ट परिणाम को गुणा करने के लिए आवश्यक न्यूनतम लागत की गणना करते हैं, तो हम इसे संगृहीत करते हैं। यदि हमें कभी भी इसकी गणना करने के लिए कहा जाता है, तो हम केवल संगृहीत किया गया उत्तर देते हैं, और इसकी पुनर्गणना नहीं करते हैं। चूंकि यहाँ पर n²/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 है।

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

functools import cache से

def matrix chaimorder (dems: list [int]) -> int:

   @cache
   def a (i,j):
       return min ((a(i,k) + dims[i] * dims[k] * dims[j] + a(k,j)
                  के लिए range में (i + 1, j)), default=0)

   return a(0, len(dims) - 1)

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

   public class matrix MatrixOrderOptimization 

protected int[][]m;
protected int[][]s;

   public void matrixchainorder (int [] dims) {
       int n = dims.length - 1;
       m = new int[n][n];
       s = new int[n][n];

       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;
               for (int k = i; k <j; k++) {
                   int cost = m[i][k] + m[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
                   अगर (cost <m [i] [j]) {
                       m[i][j] = cost;
                       s[i][j] = k;
                   }
               }
           }
       }
   }

   public void printOptimalParenthesizations () {
       boolean[] inAResult = new boolean[s.length];
       PrintOptimalParenthesizations(s, 0, s.length - 1, inAResult);
   }

   void printOptimalParenthesizations(int[][]s, int i, int j, /* for pretty printing: */ boolean[] inAResult) {
        if (i != j) {
           PrintOptimalParenthesizations(s, i, s[i][j], inAResult);
           PrintOptimalParenthesizations(s, s[i][j] + 1, j, inAResult);
           String istr = inAResult [i]? "_result " : " ";
           String jstr = inAResult [j]? "_result " : " ";
           System.out.println (" A_" + i + istr + "* A_" + j + jstr);
           inAResult[i] = true;
           inAResult[j] = true;
       }
   }

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

अधिक प्रभावशाली एल्गोरिदम

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

हू और शिंग

हू और शिंग द्वारा प्रकाशित एल्गोरिद्म O(n log n) कम्प्यूटेशनल जटिलता प्राप्त करता है। उन्होंने दिखाया कि कैसे आव्यूह श्रृंखला गुणन समस्या को एक नियमित बहुभुज के त्रिभुज की समस्या में परिवर्तित (या (कम)) किया जा सकता है। बहुभुज इस तरह उन्मुख होता है कि निचला भाग क्षैतीज होता है, जिसे आधार कहा जाता है, जो अंतिम परिणाम को दर्शाता है। बहुभुज की अन्य n भुजाएँ, दक्षिणावर्त दिशा में, आव्यूहों को दर्शाती है। एक पक्ष के प्रत्येक किनारे पर शीर्ष उस पक्ष द्वारा दर्शाए गए आव्यूह के आयाम हैं। गुणन श्रृंखला में n आव्यूहो के साथ n−1 बाइनरी संचालन और C_n−1 कोष्ठक लगाने की विधिया है, जहाँ C_n−1 (n−1)-वीं कैटलन संख्या है। एल्गोरिदम C_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 n) एल्गोरिदम

वांग, झू और तियान ने एक सरलीकृत O(n log m) एल्गोरिथम प्रकाशित किया है, जहां n श्रृंखला में आव्यूह की संख्या है और m दी गई आव्यूह श्रृंखला के आयाम में स्थित न्यूनतम अनुक्रम की संख्या है।

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

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

चिन तथा हू और शिंग द्वारा बनाया गया एल्गोरीदम O(n) में कार्य करता है और एक कोष्ठक उत्पन्न करता है जो श्रेष्ठतम विकल्प से अधिकतम 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})$ भुजाओं को त्रिकोण में जोड़ देते है। यह हमें लगभग उच्चतम त्रिभुज देता है।

सामान्यीकरण

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

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

यह भी देखें

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