矩陣鏈mutiplication動態編程

Question

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n 
    Matrix-Chain-Order(int p[]) 
{ 
// length[p] = n + 1 
n = p.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] 
// cost is zero when multiplying one matrix 
for (i = 1; i <= n; i++) 
    m[i,i] = 0; 

for (L=2; L<=n; L++) { // L is chain length 
    for (i=1; i<=n-L+1; i++) { 
     j = i+L-1; 
     m[i,j] = MAXINT; 
     for (k=i; k<=j-1; k++) { 
      // q = cost/scalar multiplications 
      q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]; 
      if (q < m[i,j]) { 
       m[i,j] = q; 
       // s[i,j] = Second auxiliary table that stores k 
       // k  = Index that achieved optimal cost 
       s[i,j] = k; 
      } 
     } 
    } 
} 
} 

這是矩陣查寧乘法 的僞碼我不能明白這部分

for (L=2; L<=n; L++) { // L is chain length 
    for (i=1; i<=n-L+1; i++) { 
     j = i+L-1; 
     m[i,j] = MAXINT; 

爲什麼採取i到小於或等於（N-L + 1） 和j = I + L-1

是所有的初學者

Answer 1

首先，它的僞代碼，並且這些陣列是基於1的。如果您使用的是C語言，那麼這可能是第一個問題，因爲C中的數組起始於索引0並結束於len-1，如果len是數組的長度。接下來，變量n被選擇爲小於矩陣的總數1。如果您用p.length - 1替換n，那麼它可能會變得更清晰一些。

1. 您要運行對所有可能的鏈長的外環（即鏈長L）。您從最小的鏈長開始（只有兩個矩陣）並以所有矩陣結束（即L從2到n）。在此之前，對於僅有一個矩陣的簡單情況（即無乘法），將成本數組初始化。

2. 這意味着i可以從1去，直到最後一項減去鏈長（n-L+1，注意n是p.length - 1所以這是有效p.length - L）。例如，如果你正在檢查長度4鏈，你i循環將有效地運行是這樣的：

   L = 4; 
   for (i = 1; i <= p.length - 4; i++) 
   { 
       ... 
   } 
   

   在C語言中，你會寫for (i = 0; i < p.length - 4; i++)。請注意，<=被替換爲<。

3. 接下來，您試圖獲得從i開始，長度爲L的乘法鏈的成本。這意味着鏈中的最後一個元素是j = i + L -1。再次，如果當前鏈長爲L，那麼你有：

   L = 4; 
   for (i = 1; i <= p.length - 4; i++) 
   { 
       j = i + 3; 
       ... 
   } 
   

   換句話說，如果i是10，您想j爲13，因爲這是（長度爲4的鏈10,11,12 ，13）。

4. 最後，您需要檢查i和j之間的所有鏈條的成本。這就是爲什麼k從i到j-1。對於具有鏈長L=4的例子中，您有：

   L = 4; 
   for (i = 1; i <= p.length - 4; i++) 
   { 
       j = i + 3; 
       m[i,j] = MAXINT; 
       for (k = i; k <= j - 1; k++) 
       { 
        // get the cost of splitting at `k`, 
        // i.e. chains (i, k) and (k + 1, j) 
       } 
   } 
   

   換句話說，如果L爲4，i爲10，j爲13，要測試鏈(10)(11,12,13)，(10,11)(12,13)和(10,11,12)(13)。因此k必須從i到j-1。