問題描述

給定n個(gè)矩陣：A1,A2,...,An，其中Ai與Ai+1是可乘的，i=1，2...，n-1。確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。

矩陣乘法的順序安排

對于圖像處理來說，矩陣運(yùn)行是中必不可少的重要數(shù)學(xué)方法，另外在神經(jīng)網(wǎng)絡(luò)、模式識別等領(lǐng)域也有著廣泛的用途。在這里就先來簡單復(fù)習(xí)一下矩陣的相關(guān)知識：

矩陣乘法

在矩陣乘法中，第一個(gè)矩陣的行數(shù)和第二個(gè)矩陣的列數(shù)必須是相同的。先來看一個(gè)簡單的例子：

之所以這樣要求，是因?yàn)榫仃嚨某朔ǘx中，就要求了，第一個(gè)矩陣每一行和第二個(gè)矩陣每一列相對應(yīng)位置的數(shù)字做乘的操作：

如果A矩陣是p×q的矩陣，B是q×r的矩陣，那么乘積C是p×r的矩陣。它們一共計(jì)算了p×q×r次。

以下是一段計(jì)算兩個(gè)矩陣乘積的標(biāo)準(zhǔn)算法：

void matrixMultiply(int[][] matrixA, int[][] matrixB,int[][] matrixC,int ra, int ca, int rb, int cb) {
    if (ca != cb) {
        System.err.println("矩陣不可乘！");
        return;
    }   // end if

    for (int i = 0; i < ra; i++) {
        for (int j = 0; j < cb; j++) {
            int sum = matrixA[i][0] * matrixB[0][j];
            for (int k = 0; k < ca; k++) {
                sum += matrixA[i][k] * matrixB[k][j];
            }   // end for
            matrixC[i][j] = sum;
        }
    }
}

順序安排

假設(shè)給定3個(gè)矩陣，A、B、C，它們的規(guī)模分別是10×100、100×5和5×50。

• 如果按照((AB)C)的順序計(jì)算：
  為計(jì)算AB（規(guī)模10×5），需要做10×100×5=5000次標(biāo)量乘法，再與C相乘又需要做10×5×50=2500次標(biāo)量乘法， 共需要7500次標(biāo)量乘法。
• 如果按照(A(BC))的順序計(jì)算：
  為計(jì)算BC（規(guī)模100×50），需要做100×5×50=25000次標(biāo)量乘法，再與A相乘又需要做10×100×50=50000次標(biāo)量乘法，共需要75000次標(biāo)量乘法。

因此，按第一種順序計(jì)算矩陣連乘要比第二種順序快10倍。所以，進(jìn)行一些計(jì)算來確定最有順序還是值得的。

動態(tài)規(guī)劃法

設(shè)m_Left,Right是進(jìn)行矩陣乘法A_LeftA_Left+1···A_Right-1A_Right所需要的乘法次數(shù)。為一致起見，m_Left,Left=0。設(shè)最后的乘法是（A_Left···A_i）（A_i+1A_Right），其中 Left ≤ i ≤ Right。

此時(shí)所用的乘法次數(shù)為：m_Left,i + m_i+1,Right + c_Left-1c_ic_Right。這三項(xiàng)分別代表計(jì)算（A_Left···A_i）、（A_i+1A_Right）以及它們的乘積所需要的乘法。除了最后的答案，還要顯示實(shí)際的乘法順序，所以我們還要記錄i的值，由此得到以下算法：

public static void optMatrix(int[] c, long[][] m, int[][] lastChange) {
    int n = c.length - 1;

    for (int left = 0; left < n; left++) {
        m[left][left] = 0;
    }
    for (int k = 1; k <= n; k++) {
        for (int left = 1; left <= n - k; left++) { // k is right - left，即子問題規(guī)模
            // For each postion
            int right = left + k;
            m[left][right] = INFINITY;              // 置為無窮大
            for (int i = left; i < right; i++) {    // i為斷開位置
                long thisCost = m[left][i] + m[i + 1][right] +
                        c[left - 1] * c[i] * c[right];

                if (thisCost < m[left][right]) {    // Update min
                    m[left][right] = thisCost;
                    lastChange[left][right] = i;
                }
            }
        }   // end inner for
    }   // end outer for
}

這個(gè)程序包含三重嵌套循環(huán)，容易看出它以O(shè)(N³)時(shí)間運(yùn)行。這里其實(shí)有更快地算法，但由于執(zhí)行具體矩陣乘法的時(shí)間仍然很可能會比計(jì)算最有順序的乘法的時(shí)間多得多，所以這個(gè)算法還是挺實(shí)用的。

歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處！
簡書ID：@我沒有三顆心臟
github：wmyskxz
歡迎關(guān)注公眾微信號：wmyskxz_javaweb
分享自己的Java Web學(xué)習(xí)之路以及各種Java學(xué)習(xí)資料